[2293] 동전

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

---

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;

// 2293 동전 1
public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int [] DP = new int[k+1];
		int [] arr = new int[n];
		
		for(int i=0; i<n; i++) {
			arr[i] = sc.nextInt();
		}
		
		DP[0] = 1;
		
		for(int i=0; i<n; i++) {
			for(int j=1; j<=k; j++) {
				if(j>=arr[i]) DP[j] += DP[j-arr[i]];
			}
		}
		System.out.println(DP[k]);
	}
}

---

동적 계획법을 사용해서 해결하는 문제이다. 1, 2, 5의 가치를 가진 동전을 가지고 10을 만드는 경우의 수를 구하는 예제를 통해서 이해해보자.

< 문제 풀이 >

1. 1원 한가지만 가지고 1부터 10까지 만들 수 있는 경우의 수는 1가지 이다.

2. 1, 2원을 가지고 1부터 10까지 만들 수 있는 경우의 수는 2부터 1원 한가지만 가지고 만든 경우의 수에 1이 추가 되고, 2의 배수인 수를 만드는 경우의 수에 한가지씩 더 추가가 된다. 

3. 1, 2, 5원을 가지고 만드는 경우의 수도 마찬가지로 5까지는 1, 2원을 가지고 만드는 경우의 수와 같지만 5보다 클 때, 경우의수가 1개씩 추가되고, 5의 배수인 경우의수에 한가지씩 더 추가 된다.

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