[백준] 11047번 동전 0 for JAVA - 탐욕 알고리즘 적용한 풀이

 

문제설명

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

 

제한사항

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

 

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

 

문제풀이

동전이 오름차순으로 정렬되어 입력되기 때문에 뒤에서부터 동전이 계산 가능한지 확인한다.

1. input 배열을 뒤에서부터 탐색
2. n번째 input 값이 K보다 작다면, K/input[n] 값을 결과값에 더함
3. n번째 동전으로 계산 가능한만큼 K를 뺌
4. K가 0과 같거나 n이 0보다 작다면 반복 종료 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static StringTokenizer st;
	static int N, K, res, input[];
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		input = new int[N];
		res = 0;
		
		for (int n = 0; n < N; n++) {
			input[n] = Integer.parseInt(br.readLine());
		}
		int n = N-1;
		while(n>=0 && K != 0) {
			if(K>=input[n]) {
				int divide = K/input[n];
				res += divide;
				K -= divide * input[n];
			}
			n--;
		}
		
		System.out.println(res);
		br.close();
	}
}

 

마치며

탐욕(Greedy) 알고리즘은 최적해를 구하는 데 사용되는 근시안적인 방법입니다. 

그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적이 해답에 도달합니다.

 

문제 바로가기

11047번: 동전 0