[Java] 백준 2293번 동전1

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

2293번: 동전 1

문제 설명

• n가지 종류의 동전을 사용해서 K원을 만들 수 있는 경우이 수 구하기 (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 
• 동전 사용 갯수는 상관없다.
• 동전의 구성이 같으면 순서 상관없이 같은 경우 -> 2원+1원과 1원+2원은 같은 경우이다.

 

동전1(1원)로 k(1~10)원을 만들 수있는 경우의 수는 자기 자신으로 각 한 가지이다.

1원	2원	3원	4원	5원	6원	7원	8원	9원	10원
1	1	1	1	1	1	1	1	1	1

동전2(2원)가 추가 되었을때 동전1과 동전2로 k원을 만들 수있는 경우의 수는 다음과 같다.

1원	2원	3원	4원	5원	6원	7원	8원	9원	10원
1	2	2	3	3	4	4	5	5	6

1. 동전1과 동전2로 1원을 만들 수 있는 경우의 수는 1원x1 1가지이다.

2. 동전1과 동전2로 2원을 만들 수 있는 경우의 수는 (1원X2, 2원X1)로 2가지이다.

3. 동전1과 동전2로 3원을 만들 수 있는 경우의 수는 (1원X3, 2원X1+1X1)로 2가지이다.

4. 동전1과 동전2로 4원을 만들 수 있는 경우의 수는 (1원X4, 2원X2, 2원X1+1X2)로 3가지이다.

5. 동전1과 동전2로 5원을 만들 수 있는 경우의 수는 (1원X5, 2원X2+1X1, 2원X1+1X3)로 3가지이다.

. 

.

.

10. 동전1과 동전2로 10원을 만들 수 있는 경우의 수는 (1원X10, 2원X5, 2원X4+1X2, 2원X3+1X4, 2원X2+1X6, 2원X1+1X8)로 6가지이다.

 

 

동전3(5원)가 추가 되었을때 동전1,동전2 그리고 동전3으로 k원을 만들 수있는 경우의 수는 다음과 같다.

1원	2원	3원	4원	5원	6원	7원	8원	9원	10원
1	2	2	3	4	5	6	7	8	10

 

N번째 동전을 써서 K원을 만드는 경우의 수는 N-1번째까지 동전을 써서 K원을 만드는 경우의 수 +  N번째까지 동전을 써서 (K-coin[i])원을 만드는 경우의 수

즉, 찾을 수 있는 규칙은 dp[i] += dp[i-coin[i]]이다. 

 

import java.util.Scanner;

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