그리디: 동전0 (백준 11047)

○ 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 256 MB 112366 59201 45630 51.980%

○ 문제
준규가 가지고 있는 동전은 총 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

○ 입력 예제
10 4200
1
5
10
50
100
500
1000
5000
10000
50000

○ 출력 예제
6

---

import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		//동전 종류 N개, 합계금액 K원 입력
		int num = sc.nextInt();
		int sum = sc.nextInt();
		
		//동전 종류 N개 배열 입력
		int[] amt = new int[num];
		int i = 0;
		while (sc.hasNextInt() && i < num) {
			amt[i++] = sc.nextInt();
		}
		
		//동전종류 N개로 K원을 만드는데 필요한 최소 동전 개수
		int count = 0;
		for (int j = num-1; j >= 0; j--) {
			if (sum >= amt[j]) {
				count += (sum / amt[j]);
				sum = sum % amt[j];
			}
		}
		
		System.out.println(count);
		
	}
	
}

○ 확인
- 동전 0 문제는 배수 관계이기 때문에 그리디 알고리즘 적용이 가능
- for문 역으로 사용 시 변수 초기화 값 주의
- 나누기와 몫을 이용하여 연산