BaekJoon _백준 9084 > DP> #35 동전

동전

문제:https://www.acmicpc.net/problem/9084

알고리즘 종류 : DP

1. 문제 설명

우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 1원짜리 30개 또는 10원짜리 2개와 5원짜리 2개 등의 방법이 가능하다.

동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오.

2. 나의 코드

- Weight or Value 가 배열의 인덱스가 될 수 있다.

-  점화식 D[i] = D[i] + D[i - a[j]];

- 배열 D는 i 원을 가질때, 동전을 집을 수 있는 모든 경우의 수

- 배열 a는 각 동전의 가치

- 주어진 동전이 {1,5,10}이 있을때,

- 초기 배열 D는 0으로 초기화 하자.

- D[30] 가 1원만 가지고 30원을 만들 수 있는 모든 경우의 수라 가정하자. 이때, 10원을 1개 추가하여, 여러개의 1원과 10원 1개를 추가하여 30을 만든다고 한다면,

- D[30] = D[30](원래 1원만을 가지고 만들 수 있는 경우의 수) + D[30 - 10](10원을 추가 했으니 20원을 만들 수 있는 경우의 수가 된다.)

- D[0] = 1이다. D[1 - 1] = 해당 동전의 가치를 만들 수 있는 경우의 수는 항상 1개이므로. => D[1] = D[1] + D[1-1];

import java.util.*;

class Main{
	public static void main(String [] args){
		Scanner sc = new Scanner(System.in);
		int T;
		int N;
		int [] cost;
		int val;
		int [] answer;

		T = sc.nextInt();
		answer = new int[T];

		for(int i=0;i<T;i++){
			N= sc.nextInt();
			cost = new int[N];
			for(int j=0;j<N;j++){
				cost[j]=sc.nextInt();
			}
			val = sc.nextInt();
			int [] d = new int[val+1];
			d[0] = 1;
			for(int k=0;k<N;k++){
				for(int h=cost[k];h<val+1;h++){
					d[h] = (d[h] + d[h - cost[k]]);
				}
			}
			answer[i] = d[val];
		}
		for(int i=0;i<answer.length;i++){
			System.out.println(answer[i]);
		}
	}
}

3. 보완

DP는 너무 여렵다.