[JAVA] 백준 2293번 : 동전 1

2293번: 동전 1

문제

- n가지 종류의 동전이 주어지고, 각각의 동전이 나타내는 가치는 다를 때, 그 가치의 합이 k원이 되도록 하는 그 경우의 수를 구하는 프로그램.

- 각각의 동전은 몇 개라도 사용가능

- 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우로 침.

 

입력

- 첫째 줄에 n, k가 주어짐. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000)

- 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. (100,000보다 작거나 같은 자연수)

 

출력

첫째 줄에 경우의 수를 출력. (경우의 수는 2^31보다 작다.)

 

 

풀이

 

n=3 , k=5 이고 주어진 동전의 가치를 1,2,5라고 가정했을 때, 가치의 합이 k원이되는 경우의 수를 구한다고 하면

dp[5-coin[0]] 은 가치가 1원인 동전만을 이용했을 때,

dp[5-coin[2]] 은 가치가 1,2원인 동전만을 이용했을 때 같은 식으로 방법을 유도해냈다.

 

따라서, DP[k] = DP[k-coin[0]] + DP[k-coin[1]] + … + DP[k-coin[n-1]] 이다.

 

즉, 새로운 동전이 coin[n-1] 추가될때마다

DP[k] = DP[k](기존의 동전 이용했을때) + DP[k-coin[n-1]](새로 추가한 동전을 포함해 이용했을 때) 이(가) 되는 셈이다.

 

아래 코드에서는 배열 coin[] 에 0번째가 아니라 1번째부터 동전의 가치가 저장되도록 했다.

public class bj2293 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner s = new Scanner(System.in);
		
		int n = s.nextInt(); // n 입력받음 , 동전의 가짓수
		int k = s.nextInt(); // k 입력받음, 
		
		int coin[] = new int[101]; // 동전의 가치
		int dp[] = new int[10001]; // n가지 종류의 동전을 사용해 k원이 되게하는 경우의 수
		
		for(int i=1;i<=n;i++) {
			coin[i]=s.nextInt();
		}
		
		dp[0] = 1;
		for(int i=1;i<=n;i++) { 
			for(int j=coin[i];j<=k;j++){	
				dp[j] += dp[j-coin[i]];
			}
		}
		
		System.out.println(dp[k]);
		s.close();
		
	}

}