[Java] 백준 2293 : 동전 1

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

2293번: 동전 1

---

 

동전별로 k값을 만드는 경우의 수를 구해본다.

 

 

예제 입력에서의 동전 종류는 1,2,5이다.

1,2,5의 종류로 1~K까지의 수를 만들 수 있는 경우의 수를 구한다. 

 

 

 

 

 

 

동전을 가지고 만들 수 있는 경우의 수를 찾아서 표를 채워주었다. 

 

- 동전 1을 가지고 1~10까지의 수를 만들 수 있는 경우의  수

- 동전 1과 2를 가지고 1~10까지의 수를 만들 수 있는 경우의  수

 

- 동전 1과 2,5 를 가지고 1~10까지의 수를 만들 수 있는 경우의  수

 

각각의 값은 이전 동전들을 가지고 경우의 수를 구했을  때의 값을 사용하여 구할 수 있다는 점을 기억하여 규칙을 찾아내면 된다.

 

표는 2차원의 배열이지만 사용할 dp []는 1차원으로 

이 값만이 dp []에 남아 있을 것이다. 

 

이 계산의 규칙은 dp [i]는 해당 dp [i]에 현재 구하는 동전의 값만큼 앞에 있는 dp의 값을 더한 것이 같다.

예를 들어, 현재 동전 2를 가지고 dp [5]를 구하려면 dp [5]의 현재 값인 1과 dp [5-2]=dp [3]=2의 값을 더하면 3을 얻을 수 있다.

즉, 이 규칙의 점화식은 dp [i]=dp [i]+dp [i-coin [j]]인 것이다.

근데 동전의 크기가 i 보다 작으면 범위에서 벗어나기 때문에 if절로 범위 내에서만 계산할 수 있게 해줘야 한다. 

 

---

import java.io.*;

public class Main {
	static int N,K;
	static int[] coin,dp;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] str1 = br.readLine().split(" ");
		N = Integer.parseInt(str1[0]);	// 동전 종류
		K = Integer.parseInt(str1[1]);	// 목표 값
		
		coin = new int[N];
		dp = new int[K+1];
		
		for(int i=0; i<N;i++) {	//코인 종류
			coin[i]=Integer.parseInt(br.readLine());
		}
		
		dp[0]=1;
		
		for(int i=0; i<N;i++) {	//코인 종류별
			for(int j=1;j<=K;j++) {	//1~K
				if(j>=coin[i]) {
					dp[j]+=dp[j-coin[i]];
				}
			}
		}
		
		System.out.println(dp[K]);
		

	}// main()
		
}// class Main