문제

---

이해

---

목표 금액인 K를 맞추기 위해 N개의 동전이 주어진다.

N개의 동전은 각각 가치가 다르다.

주어진 동전을 활용하여 K원이 되는 동전 조합의 경우의 수를 구하여라.

접근

---

DP 문제가 생각하기 어려운 것 같다..

처음에 감이 도저히 잡히지 않아서 이것저것 시도해보았다.

동전 중 하나만 사용하기, 둘만 사용하기,,,, 다 사용하기,, 이런식으로도 접근해봤지만 N이 최대 100까지 가능하기 때문에 불가능해 보였다.

인터넷을 찾아보니 동전을 활용하는 기준을 두고 테이블을 만들었다.

기준은 동전1만 사용하기, 동전1, 2만 사용하기,,,,

내가 세운 기준처럼 무조건 사용하는 것이 아닌 허용하는 식으로 DP 테이블을 작성했다.

아래는 예제에 대한 DP 테이블이다.

첫번째 1만 사용했을 때는 당연하게도 1가지 경우밖에 존재하지 않는다.

두번째 1과 2를 사용했을때는 특정한 시점에 값이 커지는 것을 알 수 있다.

왜그런지 한번 보자.

1원과 2원으로 2원을 만들때 1 + 1, 2 로 총 두가지가 존재할 수 있다.

이를 다른 관점에서 바라봐보자.

1원과 2원으로 2원을 만들때는 당연하게도 1원으로만 구성하기, 2원을 포함하여 구성하기로 두 가지 케이스가 존재한다.

케이스 첫번째, 1원으로만 구성하기는 ((1), 2)의 값인 1이다.

케이스 두번째, 2원을 포함하여 구성하기는 전체 금액인 2원에서 2원을 빼고 0원을 아무렇게나 구성하면 된다. 이때의 값은 ((1,2), 0)이 되는 것이다.

따라서, 1 + 1 = 2가 도출되는 것이다.

이를 다른 케이스에도 적용시켜보자.

1원과 2원으로 6원 구성하기

1. 1원으로만 구성하기
2. 2원을 포함하고 4원을 1원과 2원으로 구성하기
   => 1 + 3 = 4

그럼 위의 과정을 점화식으로 나타내면 다음과 같다.

DP[N] = DP[N] + DP[N - 포함될 동전값]

이 문제에서는 DP값을 동전을 하나씩 포함시킬때마다 갱신하는 과정이 있다. 이는 이전에 풀었던 슬라이딩 윈도우 방식과 유사하다.

반복문을 전체 동전이 포함되는 경우까지 진행하여 최종적으로 다 포함했을 때의 DP값을 구할 수 있다.

코드

---

package java_baekjoon;

import java.util.*;
import java.io.*;

public class prob2293 {
  public static void main(String[] args) throws IOException {
    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[] dp = new int[K + 1];
    dp[0] = 1;
    List<Integer> coin = new ArrayList<>();

    for (int i = 0; i < N; i++) {
      coin.add(Integer.parseInt(br.readLine()));
    }

    for (int i = 0; i < coin.size(); i++) {
      for (int j = coin.get(i); j <= K; j++) {
        dp[j] += dp[j - coin.get(i)];
      }
    }

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

결과

---