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]);
}
}
'알고리즘' 카테고리의 다른 글
[Java] 백준 3036번 링 (0) | 2020.05.17 |
---|---|
[Java] 백준 14501번 퇴사 (0) | 2020.05.17 |
[Java]백준 1932번 정수삼각형 (0) | 2020.05.17 |
[Java]백준 11726번 2Xn 타일링(Dynamic Programming) (0) | 2020.05.08 |
[Java] 백준 9461번 (Dynamic Programming) (0) | 2020.05.08 |
댓글