백준 풀이 : 동전 1 - 2293번

 

이 문제는 방법의 수를 구하는 문제로 DP 문제이다.

n개의 동전으로 k원을 만드는 방법의 수를 구해야 한다.

예제인 n = 3, k = 10, coin = {1, 2, 5}로 설명해보겠다.

 

처음에 나는 dp[i] = dp[i-1] + dp[i - 2] + dp[i - 5] 이런 식으로 생각했는데 그럼 dp[3] = 2가 말이 되지 않았다.

 

이 문제는 해당 수를 각 동전으로 만들 수 있는 경우의 수의 합으로 생각하면 된다.

해당 수의 모든 경우의 수를 구하고 그걸 다음 계산에 사용하는 것이 아닌,

한 동전을 사용해 해당 수를 만드는 경우를 계산한 다음, 그걸 다른 수 계산에 이용해야한다.

 

즉 dp[3] = dp[2] + dp[1] 이긴 한데, 계산 당시 dp[2] = 1, dp[1] = 1이다.

왜냐하면, 이때 dp[2]는 2를 1만 사용해서 만든 경우의 수이기 때문이다.

 

같은 방법으로 dp[4] = dp[3] + dp[2]인데 이때 dp[3] = 1이고, 이때 2를 만들 수 있는 경우는 2를 사용한 경우까지 계산해서 2이므로 dp[2] = 2여서 dp[4] = 3이 된다.

 

또 dp[5] = dp[4] + dp[3] + dp[0] = 1 + 2 + 1 = 4

 

코드로는 다음과 같다.

 

키포인트는 동전 별로 만들 수 있는 경우의 수를 차례로 합산한다는 것이다.

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

public class Main {

	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[] coin = new int[n];
		int[] dp = new int[k+1];
		dp[0] = 1;
		
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			coin[i] = Integer.parseInt(st.nextToken());
		}
		
		for(int oneCoin : coin) {
			for(int i = oneCoin; i <= k; i++) {
				dp[i] += dp[i - oneCoin];
			}
		}
		
		System.out.println(dp[k]);
		
	
	}
}