알고리즘 3주차

문제번호 : 16173

• 알고리즘 : 스택
• 난이도 : 실버 4

문제

16173

접근

가정

풀어보기

시행착오

참고자료

---

문제번호 : 14916번

• 알고리즘 : 그리디 알고리즘
• 난이도 : 실버5

문제

14916

접근

• 그리디 알고리즘
  • 근사 알고리즘
  • 최적의 해를 보장하지 않음
  • 지금 이 순간 당장 최적인 답을 선택

가정

• Map 을 이용해서 동전에 따라 갯수를 저장
• 거스름돈 판별
• 나누어 떨어지지 않을 경우 큰 동전을 -1

풀어보기

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.HashMap;  
import java.util.Map;  
  
public class Main {  
    public static void main(String[] args) throws IOException {  
  
       int price = 0;  
       int change = 0;      // 거스름돈  
  
       Map<String, Integer> map = new HashMap<>();  
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
       price = Integer.parseInt(br.readLine());  
  
       change = setUp(map, price);  
  
       if (change == 0) {  
          System.out.println(map.get("5"));  
          System.exit(0);  
       }  
  
       while (map.get("5") >= 0) {  
          // 거스름돈 판별  
          if (countChange(map, change)) {  
             System.out.println(map.get("5") + map.get("2"));  
             break;  
          } else {  
             // 나누어 떨어지지 않으면 5원을 빼고 거스름돈에 추가   
		     map.put("5", map.get("5") - 1);  
             change += 5;  
          }  
  
       }  
       if (map.get("5") == -1)  
          System.out.println("-1");  
  
    }  
    //5원 갯수와 거스름돈을 구함  
    public static int setUp(Map<String, Integer> map, int price) {  
       map.put("5", 0);  
       map.put("2", 0);  
       map.put("5", price / 5);  
       return price - ((map.get("5")) * 5);  
  
    }  
    // 거스름돈을 2원으로 나누어 떨어질 때 true 를 리턴  
    public static boolean countChange(Map<String, Integer> map, int change) {  
       if (change % 2 == 0) {  
          map.put("2", change / 2);  
          return true;  
       } else {  
          return false;  
       }  
  
    }  
  
}

시행착오

• 없음

참고자료

• System.exit(0); 정상 종료
• System.exit(1); 비정상 종료

---

문제번호 : 15965번

• 알고리즘 : ? ()
• 난이도 : 실버 2

문제

1406번

접근

• 아리스토테네스의 체
• https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

가정

• 초기값 설정 메소드 필요
• K번째 수 체크 필요
• I의 배수를 없애는 메소드 필요

풀어보기

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
  
public class Main {  
    public static void main(String[] args) throws IOException {  
  
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
       int number = Integer.parseInt(br.readLine());  
       int max = 7500000;  
       int counter = 0;  
       boolean result = false;  
  
       int[] primeNumber = new int[max];  
  
       setUp(primeNumber);  
  
       for (int i = 2; i < max; i++) {  
          if (primeNumber[i] == 1) {  
  
             counter++;  
             checkNumber(number, counter, i);  
             changeValue(primeNumber, i, max);  
  
          }  
  
       }  
  
    }  
  
    // 초기값  
    public static void setUp(int[] primeNumber) {  
       for (int i = 2; i < primeNumber.length; i++) {  
          primeNumber[i] = 1;  
       }  
  
    }  
    // K 번째 수인지 확인  
    public static void checkNumber(int number, int counter, int i) {  
       if (number == counter) {  
          System.out.println(i);  
          System.exit(0);  
       }  
  
    }  
    // i의 배수 = 0 으로 만듬  
    public static void changeValue(int[] primeNumber, int i, int max) {  
       for (int j = i; j < max; j += i) {  
          primeNumber[j] = 0;  
       }  
    }  
  
    // //소수 판별  
    // public static boolean checkPrimeNumber(int number) {  
    //     for (int i = 2; i < number + 1; i++) {    
    //        if (number % i == 0)    
    //           return false;    
    //    
    //     }    
    //     return true;    
    // }  
}

시행착오

• Map 을 썼으나 메모리 초과
• 소수 판별을 하려다 시간 초과가 됨

참고자료

• 앞쪽에 첨부함