동전
문제: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는 너무 여렵다.
