[JAVA] 백준 (골드4) 2293번 동전 1

링크

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

---

문제 설명

정답률 47.716%
n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

---

입력 예제

3 10
1
2
5

---

출력 예제

10

---

풀이

동전 1, 2, 5원으로 10원을 만드는 방법의 수를 생각해볼 때 우선 1원부터 잘게 쪼개서 생각해본다. 우선 1원만 사용해서 1원부터 10원을 만드는 방법을 생각해보면 모든 경우는 1가지가 된다.

• 1원 = 1
• 2원 = 1 + 1
• 3원 = 1 + 1 + 1
  ...
• 10원 = 1 + 1 + 1 + ... + 1

이때 2원을 사용하는 경우도 생각해보면 우선 1원은 2원으로 만들 수 없으니 스킵한다.

• 2원 -> 2가지
  • 1 + 1 -> dp[2]
  • 2 -> dp[2 - 2]
• 3원 -> 2가지
  • 1 + 1 + 1 -> dp[3]
  • 1 + 2 -> dp[3 - 2]
• 4원 -> 3가지
  • 1 + 1 + 1 + 1 -> dp[4]
  • 1 + 1 + 2 -> dp[4 - 2]
  • 2 + 2 -> dp[4 - 2]
• 5원 -> 3가지
  • 1 + 1 + 1 + 1 + 1 -> dp[5]
  • 1 + 1 + 1 + 2 -> dp[5 - 2]
  • 1 + 2 + 2 -> dp[5 - 2]
    ...

2원을 추가해 3원을 만드는 방법의 수는 1원으로 만드는 방법(1 + 1 + 1)에 1원을 만드는 방법의 수를 추가하는 것이 된다. 마찬가지로 5원을 만드는 방법의 수는 1원으로 만드는 방법에 3원을 만드는 방법의 수를 추가하는 것이 된다.

즉, j원짜리 동전으로 i원을 만드는 방법의 수는 기존의 i원을 만드는 방법의 수에 i-j원을 만드는 방법의 수를 합한 값이 된다.

이것을 DP로 구현하면 다음과 같다.

int[] dp = new int[k + 1];  //dp[i]: i원을 만들 수 있는 방법의 수
dp[0] = 1;  //0원을 만드는 방법의 수는 1
for (int coin : coins) {
    for (int i = coin; i <= k; i++) {
        dp[i] += dp[i - coin];
    }
}

전체 코드

//백준
public class Main {

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        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[] coins = new int[n];

        for (int i = 0; i < n; i++) {
            coins[i] = Integer.parseInt(br.readLine());
        }

        int[] dp = new int[k + 1];  //dp[i]: i원을 만들 수 있는 방법의 수
        dp[0] = 1;  //0원을 만드는 방법의 수는 1
		
        //중복 조합
        for (int coin : coins) {
            for (int i = coin; i <= k; i++) {  //해당 동전으로 만들 수 있는 금액의 경우의 수 누적
                dp[i] += dp[i - coin];
            }
        }

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