[백준(baekjoon) 11047] 동전 0

문제

백준 11047

N개의 종류의 동전의 가치 Ai가 주어질 때 (각 종류의 동전은 무한히 많다.) 동전 들을 사용해 K원을 만들려고 한다.
이때, 필요한 동전 종류 개수의 최소 값은?

• 주의 : A1 = 1은 Default이며, i > 1을 만족하는 Ai = Ai-1의 배수이다.

해결

처음에는 DP를 사용해야 하나 했다.
N = 3, K = 2000, A1 = 100, A2 = 500, A3 = 800의 경우
정답은 A2 * 4 = 2000이 되기 때문에.

하지만, 역시 문제는 자세히 읽어야 한다…!

i > 1을 만족하는 Ai = Ai-1의 배수이다.

이 부분에 의해서 그리디 알고리즘으로 문제를 해결할 수 있다.
가장 큰 동전 종류부터 확인, 차액을 구하여 계속 계산하면 된다.

알고리즘

그리디 알고리즘

‘탐욕 알고리즘’이라고도 불리는 그리디 알고리즘은
혹시 정답이 아닐까봐 저장해두고 모든 경우를 확인하는 DP와 달리,
그 순간에 집중해서 “이게 정답일거야!!!!” 하고 최적의 선택을 하는 것을 말한다.

그렇기 때문에 최종적으로는 답이 아닐수도 있다.
따라서 왜 이게 최적의 답이 되는지 증명이 가능해야 할 것이다.
하지만, 사용한다면 시간이 다른 알고리즘에 비해 빠르다.

구현 java

조금 더 시간을 줄이기 위하여, 금액보다 큰 동전은 배제하였다.

1.import java.util.*;
2.
3.public class Main {
4.    public static void main(String[] args) {
5.        Scanner sc = new Scanner(System.in);
6.        int n = sc.nextInt();
7.        int k = sc.nextInt();
8.        int maxAble = 0; // k보다 큰 동전은 필요없으므로 시간 줄이기 위해서
9.
10.        int[] coin = new int[n];
11.        int answer = 0;
12.        for (int i = 0; i < n; i++) {
13.            coin[i] = sc.nextInt();
14.            if (coin[i] <= k) maxAble = i;
15.        }
16.
17.        for (int i = maxAble; i >= 0; i--) {
18.            answer += k / coin[i];
19.            k %= coin[i];
20.        }
21.        System.out.println(answer);
22.    }
23.}

결과