알고리즘
[Java] 백준 2293번 동전 1 (Dynamic Programming)
태풍사랑
2020. 5. 8. 22:40
2293번: 동전 1
첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.
www.acmicpc.net
풀이
1원 = 1
2원 = 1 + 1 = 2
3원 = 1 + 1 + 1 = 2 + 1
4원 = 1 + 1 + 1 + 1 = 2 + 2
5원 = 1 + 1 + 1 + 1 + 1 = 2 + 2 + 1
6원 = 1 + 1 + 1 + 1 + 1 + 1 = 2 + 2 + 2 ....
만약 5원을 구한다고 하면
- 4원에서 +1 -> 1가지
- 3원에서 +2 -> 2가지
- 0원에서 +5 -> 1가지
=> 총 4가지
N번째 동전을 써서 K원을 만드는 경우의 수는
∴ dp[i] += dp[i-coin[i]]
public class algo_2293_dp {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), k = sc.nextInt(), coin;
int[] dp = new int[k+1];
dp[0] = 1;
for(int i = 0; i<n; i++) {
coin = sc.nextInt();
for(int j = 1; j < k+1; j++) {
if(j >= coin)
dp[j] += dp[j-coin];
}
}
System.out.println(dp[k]);
}
}