[JAVA] BOJ 11047 동전 0

 

그리디 알고리즘은 탐욕 알고리즘이라 하여 뒤를 생각하지 않고 각 상황에서 최선의 선택만을 하는 알고리즘을 의미한다. 이 문제에서는 예제에서 주어진 4200원을 만들기 위해 4200원보다 작은 것 중 가장 큰 동전을 선택하여 (예제에선 1000원) 개수에 4200/1000 한 것을 더해주고 K = 4200%1000 = 200으로 만들어주어 K가 0이 될 때까지 위의 과정을 반복합니다. 첫 번째 동전의 값은 1이기 때문에 K가 0이 안될 가능성은 없다.

 

Input으로 주어지는 값이 많기 때문에 BufferedReader를 사용했고 출력되는 수는 한 개 밖에 없기 때문에 System.out.println을 사용했다.

 

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		int[] arr = new int[N];
		for(int i=0; i<N;i++) {
			st=new StringTokenizer(br.readLine());
			arr[i] = Integer.parseInt(st.nextToken());
		}
		int cnt =0;
		while(K>0) {
			int max =0;
			for(int i=0;i<N;i++) {
				if(arr[i]>K) {
					max=arr[i-1];
					break;
				}
				max=arr[i];
			}
			cnt += K/max;
			K= K%max;
		}
		System.out.println(cnt);
	}

}

 

K가 0이 될때까지 while loop를 돌며 arr 배열의 값(동전 값)이 K보다 작은 것 중 가장 큰 값에 max를 할당하여 계산하였다. 비교적 쉬운 문제라 그리디 알고리즘이 무엇인지 감을 익히기에 적절한 문제인 것 같다.