[정올][다이나믹] 2293, 동전 1

N개의 동전의 가치를 합하여, K원을 만드는 경우를 구한다. 

1, 2, 5 원의 동전을 이용하여 10원을 만드는 경우는 다음과 같다. 

사용동전	1	2	5	개수
1	1			1
2	1+1	2		2
3	1+1+1	1+2		2
4	1+1+1+1	1+1+2, 2+2		3
5	1+1+1+1+1	1+1+1+2, 1+2+2	5	4

5원을 만드는 경우는 위와 같다. 

1원동전 사용: 1원을 5개 사용

2원동전 사용: 3원을 만드는 경우에 2원을 더하여 생성

5원동전 사용: 0원을 만드는 경우에 5원을 더하여 생성 

	package sdk.backjun.dp;
	import java.util.Scanner;
	/**
	* 백준, 동전 1, 2293
	*
	* @author whitebeard-k
	*
	*/
	public class Problem2293 {
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int N = sc.nextInt();
	int K = sc.nextInt();
	int[] coins = new int[N+1];
	for(int i = 1; i <= N; i++)
	coins[i] = sc.nextInt();
	sc.close();
	int[] dp = new int[K+1];
	dp[0] = 1;
	for(int i = 1; i <= N; i++ ){
	for(int j = 0; j <= K; j++ ){
	if(j - coins[i] >= 0) {
	dp[j] += dp[j-coins[i]];
	}
	}
	System.out.printf("coin %d: ", coins[i]);
	for(int n : dp)
	System.out.printf("%d ", n);
	System.out.println();
	}
	System.out.println(dp[K]);
	}
	}

view raw Problem2293.java hosted with ❤ by GitHub

https://www.acmicpc.net/problem/2293