[JAVA] 백준 (골드5) 9084번 동전

링크

https://www.acmicpc.net/problem/9084

---

문제 설명

정답률 67.353%
우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 1원짜리 30개 또는 10원짜리 2개와 5원짜리 2개 등의 방법이 가능하다.

동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오.

---

입력 예제

3
2
1 2
1000
3
1 5 10
100
2
5 7
22

---

출력 예제

501
121
1

---

풀이

문제를 이해하기 위해 동전이 1, 2원이 주어지고 5원을 만들어야 한다고 생각해보자. 우선 동전 1원으로 5원을 만드려면 1 + 1 + 1 + 1 + 1로 1가지이다. 다음으로 2원이 추가될 경우 1 + 1 + 1 + 2, 1 + 2 + 2의 경우가 생기고 총 방법의 수는 3가지이다.

이것은 DP로 생각해보면 우선 dp배열은 다음과 같이 정의한다.

dp[i]: i원을 만드는 방법의 수 

동전 1원만 가지고 생각해보면 다음과 같다.

• 금액 0원을 만드는 방법은 1가지(아무 동전도 안 쓰는 방법)
  dp[0] = 1
• 금액 1원을 만드는 방법은 dp[1] += dp[0] (0 + 1)
  dp[1] = 1
• 금액 2원을 만드는 방법은 dp[2] += dp[1] (1 + 1)
  dp[2] = 1
• 금액 3원을 만드는 방법은 dp[3] += dp[2] (1 + 1 + 1)
  dp[3] = 1
• 금액 5원까지 전부 계산하면
  dp = [1, 1, 1, 1, 1, 1]

여기에서 2원짜리 동전을 추가하면

• 금액 2원을 만드는 방법은 dp[2] += dp[0] (0 + 2)
  dp[2] = 2
• 금액 3원을 만드는 방법은 dp[3] += dp[1] (1 + 2)
  dp[3] = 2
• 금액 4원을 만드는 방법은 dp[4] += dp[2] (1 + 1 + 2), (2 + 2)
  dp[4] = 3
• 금액 5원을 만드는 방법은 dp[5] += dp[3] (1 + 1 + 1 + 2), (1 + 2 + 2)
  dp[5] = 3

결국 2원짜리 동전을 추가한 경우 1원짜리 동전만 사용한 방법 (1 + 1 + 1 + 1 + 1)과 3원을 만드는 방법에 2원을 추가한 방법 (1 + 1 + 1 + 2), (1 + 2 + 2)의 수의 합인 3이 된다.

이를 Bottom-Up 방식으로 구현하면 다음과 같다.

for (int coin : coins) {
    for (int i = coin; i <= M; i++) {
        //현재 동전(coin)을 추가해 i원을 만드는 방법의 수
        dp[i] += dp[i - coin];
    }
}

전체 코드

//백준
public class Main {

    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());
        for (int testCase = 0; testCase < T; testCase++) {
            int N = Integer.parseInt(br.readLine());
            int[] coins = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt)
                    .toArray();
            int M = Integer.parseInt(br.readLine());
            int[] dp = new int[M + 1];  //dp[i]: i원을 만드는 방법의 수
            dp[0] = 1;  //0원을 만드는 방법은 1가지(아무 동전도 사용X)

            for (int coin : coins) {
                for (int i = coin; i <= M; i++) {
                    //현재 동전(coin)을 추가해 i원을 만드는 방법의 수
                    dp[i] += dp[i - coin];
                }
            }

            System.out.println(dp[M]);
        }
    }
}