[BOJ 2293] 동전1

문제

• BOJ 2293
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

이 문제는 위 그림과 같이 주어진 동전을 이용해 1원부터 k원까지 만들 수 있는 경우를 적어보면 규칙을 구할 수 있다.
2원 단위로 가짓수가 하나씩 증가되고 있고, 예를 들어 6원인 경우는 4원(6원-2원)의 가짓수에서 이전의 값을 더하여 구할 수 있다.
점화식으로 표현하면 dp[j] = dp[j](기존의 동전으로 k를 만드는 경우의 수) + dp[j - coins[i]](새 동전 사용하여 k만드는 경우의 수)이 된다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

//동전1
public class Main {
	
	static int n, k; //동전종류, 가치의 합
	static int[] coins;
	static int[] dp;//인덱스: 만들 동전 가치, 값: 경우의수
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		
		coins = new int[n];
		dp = new int[k+1];
		
		for(int i=0; i<n; i++) coins[i] = Integer.parseInt(br.readLine()); //End input
		
		dp[0] = 1;//동전 0원 만들 수 있는 경우 
		
		//가치의 합이 k가 되는 경우의 수 구하기(중복 선택 가능)
		for(int i=0; i<n; i++) {
			for(int j=1; j<=k; j++) {
				if(j-coins[i] >= 0) dp[j] += dp[j-coins[i]]; 
			}
		}//End input
		
		System.out.print(dp[k]);
	}
}