[ 백준 ] 2293 동전 1

📌 Problem

주어진 동전들을 개수 제한 없이 사용하여 목표값을 만드는 경우의 수를 구하면 되는 문제로 순서와 상관없이 동일한 구성으로 이루어진 경우는 하나의 경우로 생각한다.

📌 Solution

동적 프로그래밍으로 해결하면 되는 문제이긴 하지만 한 번의 반복이 아니라 동전의 개수만큼 반복을 해야 한다. 각각의 동전을 독립적으로 실행하여 dp[n] += dp[n - coin]을 연산하면 된다. n = coin인 경우를 대비하여 dp[0] = 1로 초기화한다.

📌 Example

Example 1
예제 1번에 대한 풀이는 다음과 같다. 목표값이 10이기 때문에 10까지의 DP 배열을 만들고 dp[0] = 1로 초기화한다.

첫 번째 동전인 1에 대해 DP dp[n] = dp[n - 1]을 실행한다.

두 번째 동전인 2에 대해 DP dp[n] = dp[n - 2]를 실행한다.

세 번째 동전인 5에 대해 DP dp[n] = dp[n - 5]를 실행한다.

최종적으로 dp[10] = 10이기 떄문에 동전 1, 2, 5를 제한 없이 사용하여 만들 수 있는 서로 다른 구성의 동전 구성 개수는 10개이다.

📌 Code

StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
int N = Integer.parseInt(tokenizer.nextToken());
int T = Integer.parseInt(tokenizer.nextToken());
int[] dp = new int[T + 1];
dp[0] = 1;
while (N-- > 0) {
    int coin = Integer.parseInt(reader.readLine());
    for (int c = coin; c <= T; c++) dp[c] += dp[c - coin];
}
result.append(dp[T]);