728x90
동전 2
https://www.acmicpc.net/problem/2294
<코드>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | #include <stdio.h> int main(void){ int n, k; int Dp[10001] = {}; int coin[101]; scanf("%d %d", &n, &k); for (int i = 0; i < n; i++){ scanf("%d", &coin[i]); for (int j = 1; j <= k / coin[i]; j++) { int nowCoin = coin[i]*j; if (Dp[nowCoin] == 0) Dp[nowCoin] = j; else Dp[nowCoin] = Dp[nowCoin] < j ? Dp[nowCoin] : j; } } for (int i = 2; i <= k; i++) { for (int j = 1; j <= i / 2; j++) { if (Dp[j] != 0 && Dp[i - j] != 0){ if (Dp[i] == 0) Dp[i] = Dp[j] + Dp[i - j]; else { int temp = Dp[j] + Dp[i - j]; if (Dp[i] > temp) Dp[i] = temp; } } } } if(Dp[k]==0) printf("-1\n"); else printf("%d\n", Dp[k]); } | cs |
<문제 푼 요령>
1. 이 문제에서 중요한 것은 최소 개수를 만드는 것입니다.
2. 그렇기에 처음 Dp[i] 배열은 0으로 초기화 되어있기 때문에 이 부분에 대해서는 예외 처리 해줍니다.
3. 처음 먼저 각 숫자에 대해서 그 숫자에 배수로 Dp 배열을 채우고 이미 값이 들어가 있으면 min 값을 체크해 줍니다.
4. 그후 2 ~~ K 까지 Dp[i] = Dp[j] + Dp[i-j] 로 만들어질수도 있기때문에 이걸 만들어가면서 최소값을 비교해줍니다. 여기서 중요한것 중 하나는 Dp[j]와 Dp[i-j] 중 하나라도 0이 포함된다면 Dp[i]는 만들 수 없는 숫자가 되는 거기 때문에 예외 처리 해줍니다.
5. 이렇게 값을 구하면 Dp[k]에서 우리가 원하는 최소값을 구할수 있습니다.
728x90
'Algorithm > DP(동적 계획법)' 카테고리의 다른 글
[백준][2240번][DP] 자두나무 (0) | 2016.04.11 |
---|---|
[백준][9095번][DP] 1,2,3 더하기 (3) | 2016.04.10 |
[백준][2293번][DP] 동전 1 (1) | 2016.04.09 |
[ALGOSPOT][DP] PI (1) | 2016.04.06 |
[백준][1073번][DP] 도미노 (0) | 2016.03.30 |
댓글