[C, python] 백준 2294번 : 동전 2

문제

 

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

 

입력

 

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

 

출력

 

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

 

풀이

 

c

 

c언어로 dp를 사용하여 풀어보았습니다.

dp 배열을 최대값으로 초기화 시켜준 후 줄여가는 방식을 사용하였습니다.

1원부터 k원까지 차례로 올려가며 가지고 있는 동전의 종류를 전부 빼보는 방식인데, 인덱스로 들어가는 숫자가 0보다 작아지는 것을 방지하기 위해 조건문이 복잡해졌네요.

 

#include <stdio.h>
#include <limits.h>
 
int coin[105];
int dp[10005];
 
int main() {
    int n, k;
    scanf("%d %d", &n, &k);
 
    for (int i = 0; i <= k; i++) {
        dp[i] = INT_MAX;
    }
 
    for (int i = 0; i < n; i++) {
        scanf("%d", &coin[i]);
        if(coin[i]<=10000) dp[coin[i]] = 1;
    }
 
    for (int i = 1; i <= k; i++) {
        int temp = dp[i];
        for (int j = 0; j < n; j++) {
            if (i - coin[j] > 0 && dp[i - coin[j]] != INT_MAX && temp > dp[i - coin[j]] + 1)
                temp = dp[i - coin[j]] + 1;
        }
        dp[i] = temp;
    }
    
    if (dp[k] == INT_MAX) printf("%d\n", -1);
    else printf("%d\n", dp[k]);
}

 

같은 c언어 풀이이지만 다른 방법이 또 있습니다.

이 풀이는 돈을 기준으로 하는 것이 아니라 동전을 첫번째 for문의 조건으로 사용하는 방법입니다.

동전을 기준으로 한다면 이중 for문의 내부 반복문에서 시작을 기준 동전값보다 크게 해준다면 배열의 인덱스에 문제가 없어 더 간편하게 사용할 수 있습니다. 

 

#include <stdio.h>
#include <limits.h>
 
int coin[105];
int dp[10005];
 
int main() {
    int n, k;
    scanf("%d %d", &n, &k);
 
    for (int i = 1; i <= n; i++) scanf("%d", &coin[i]);
    for (int i = 1; i <= k; i++) dp[i] = 10005;
 
    for (int j = 1; j <= n; j++) {
        for (int i = coin[j]; i <= k; i++) {
            if (dp[i] > dp[i - coin[j]] + 1) dp[i] = dp[i - coin[j]] + 1;
        }
    }
 
    if (dp[k] == 10005) printf("%d\n",-1);
    else printf("%d\n", dp[k]);
}

python

 

c언어 풀이의 두번째 방법과 같은 방식으로 python으로 풀어보았습니다

 

coin = [0]*105
dp = [10005]*10005
dp[0] = 0
 
n, k = map(int, input().split())
 
for i in range(1,n+1):
    coin[i] = int(input())
    
for j in range(1,n+1):
    for i in range(coin[j],k+1):
        if dp[i] > dp[i-coin[j]] + 1 :
            dp[i] = dp[i - coin[j]] + 1;
            
if dp[k] == 10005:
    print(-1)
else :
    print(dp[k])
 

문제 출처 : https://www.acmicpc.net/problem/2294