[백준] 2293번 동전 1

   해당 문제의 원문은 여기서 확인하자.

 

문제 이해

   가치가 다른 n가지 종류의 동전을 이용해 가치의 합이 k원이 되는 경우의 수를 구하는 문제이다. 이때 동전의 순서는 고려하지 않는다.

   첫째 줄에 n, k가 순서대로 입력되며 다음 n개의 줄에는 각 동전의 가치가 입력된다. 제한 사항은 다음과 같다.

 

• 1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000
• 1 ≤ 동전의 가치 ≤ 100,000
• 결과 < 2^31

---

접근 방식

   DP의 개념을 이용해 해결할 수 있는 문제이다. k + 1 값을 배열의 최대 크기로 정하고 배열의 인덱스를 만들어진 가치의 합, 인덱스의 값을 만들어진 횟수로 정의한다. 다음 예시를 보자.

 

 

   최상단의 숫자는 인덱스이자 만들어질 수 있는 가치의 합들을 의미한다. 좌측의 'cost 1'은 동전의 가치를 의미하고, 배열 내에 숫자들은 해당 동전을 가지고 각 가치의 합들을 만들 수 있는 경우의 수를 의미한다. 즉, 동전의 가치가 1인 경우 각 가치의 합들을 1번씩 만들 수 있다. 인덱스 0번째가 1로 초기화된 이유는 이후에 설명한다.

   이번엔 'cost 2'를 추가해보자.

 

 

   'cost 2'의 경우 가치의 총합이 2인 경우부터 영향을 미친다. 이 경우 'cost 1'로 만드는 경우와 'cost 2'로 만드는 경우가 존재하기 때문에 2가지 경우가 가능하다.

   DP의 경우 점화식을 찾는 것이 중요한데 아직까지 감이 안 올 수 있다. 'cost 3'을 추가해보자.

 

 

   'cost 3'까지 확인해봐도 규칙을 발견하기 어려울 수 있다. 이 부분에 있어선 다양한 DP 문제를 풀어보고 그 과정에서 규칙을 찾는 연습을 충분히해야 감이 올 것이다.

   위의 예제에서 규칙을 찾아보자.

 

 

   위의 과정을 통해 알 수 있는 점은 '가치의 합의 경우의 수 = 현재 가치의 합의 경우의 수 + 현재 가치의 합에서 동전의 가치를 뺀 합의 경우의 수' 이다. 현재 가치의 합을 totalCost, 동전의 가치를 cost, 배열을 dp라고 가정하면, dp[totalCost] += dp[totalCost - cost] 라는 점화식을 얻을 수 있다.

    앞서 0번째 인덱스를 1로 초기화하고 사용하였는데 이는 점화식의 형태를 맞추기 위함이다. 만약 0번째 인덱스의 값이 0인 경우 배열의 값은 변화가 없어 모두 0으로 초기화된 상태를 유지하게 되며, 이 경우 다른 처리가 필요하게 된다.

 

※ 앞에서 변경된 인덱스 값을 뒤에 있는 인덱스 값이 초기화할 때 사용하기 때문에 1차원 배열로 DP를 처리할 수 있다.

※ 동전의 가치가 최종적으로 구하고자 하는 가치의 합보다 큰 경우를 주의해야 한다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 백준2293번 {
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer token;

    public static void main(String[] args) throws IOException {
        token = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(token.nextToken());
        int k = Integer.parseInt(token.nextToken());
        int[] dp = new int[k + 1];

        //점화식의 형태를 맞추기위해 0번째를 초기화
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            //동전의 가치 입력
            int cost = Integer.parseInt(br.readLine());
            //동전의 가치가 만들려는 가치의 합보다 큰 경우
            if (cost > k) continue;
            for (int totalCost = cost; totalCost <= k; totalCost++)
                //현재 가치의 합을 만들 수 있는 경우의 수에
                //새로운 동전의 가치를 이용해 만들 수 있는 경우의 수를 더함
                dp[totalCost] += dp[totalCost - cost];
        }
        //구하고자 하는 가치의 합의 경우의 수는 dp[k]에 저장된다.
        System.out.println(dp[k]);
    }
}