[Java] 백준 2293번 동전 1 (Dynamic Programming)

www.acmicpc.net/problem/2293

2293번: 동전 1

 

풀이

---

1원 = 1

2원 = 1 + 1 = 2

3원 = 1 + 1 + 1 = 2 + 1

4원 = 1 + 1 + 1 + 1 = 2 + 2

5원 = 1 + 1 + 1 + 1 + 1 = 2 + 2 + 1

6원 = 1 + 1 + 1 + 1 + 1 + 1 = 2 + 2 + 2  ....

 

만약 5원을 구한다고 하면

- 4원에서 +1 -> 1가지

- 3원에서 +2 -> 2가지

- 0원에서 +5 -> 1가지  

=> 총 4가지

 

N번째 동전을 써서 K원을 만드는 경우의 수는 

∴ dp[i] += dp[i-coin[i]]

 

public class algo_2293_dp {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt(), k = sc.nextInt(), coin;
		int[] dp = new int[k+1];
		
		dp[0] = 1;
		
		for(int i = 0; i<n; i++) {
			coin = sc.nextInt();
			for(int j = 1; j < k+1; j++) {
				if(j >= coin)
					dp[j] += dp[j-coin];
				}
		}
		System.out.println(dp[k]);
	}
}