2294-동전2

2294-동전2

역시 동전 문제이다. 동전1 문제는 a원을 만들수 있는 모든 경우의 수가 관심사였다면, 이번 문제는 최소 개수를 묻고 있다. 동전 금액과 목표 금액이 있고 동전 개수는 무한대라는 가정까지는 동전1과 같으나, 이번에는 목표 금액을 만드는 동전의 최소 개수를 묻는 문제이다. 따라서 dp테이블의 의미가 달라지는데 바로 

'dp[a]=b : a원을 만들기 위해 필요한 동전의 최소 개수 b개'

이다. 이러면 문제의 정답은 dp[k]가 된다.

테스트케이스의 입력처럼 1,5,12원의 동전으로 총 15원을 만들 수 있는 최소 동전 개수를 알아보자. 단순하게 생각해보면 

1원*15개 , 5원*3개 , 12원*1+1원*3개 ....가 있을텐데 정답은 5원*3개가 정답이다. 그럼 왜 이게 정답인지 역추적을 해보자. 그 이유는 15원-5원=10원을 만들 수 있는 최소 동전 개수=2 + 5원 동전 1개 이므로 총 3가지이다. 그럼 다시 10원을 만들 수 있는 최소 동전=1 + 5원 동전 1개 = 2가지. 뭐 이런식으로 계산이 된다. 즉 점화식은

dp[j]=min(dp[j],dp[j-coin[i]]+1)이다.

여기서 사소한 초기조건 처리는 min연산이 들어가니 dp[j]를 INF으로 초기화 해놓고, 목표 금액을 만들 수 없는 경우(예:100원 동전으로 1원 만들기)가 있을 경우 -1로 출력하면 되는데, 애초에 만들 수 없는 금액은 dp[j]가 INF에서 갱신이 일어나지 않았으므로 dp[]==INF이면 -1을 출력하면 된다. 그리고 이 문제도 역시 coin[]의 금액이 정렬되지 않아도 상관없이 Accept을 받을 수 있다.

아래는 for문으로 푼 bottom-up 방식이다.

#include<stdio.h>
#define INF 1<<30
int coin[110],dp[10010];
int fMin(int a, int b) {
    return a > b ? b : a;
}
int main() {
    int n, k;    scanf("%d %d", &n, &k);
 
    for (int i = 0; i < n; i++)
        scanf("%d", &coin[i]);
 
    for (int i = 0; i <= k; i++)
        dp[i] = INF;
 
    dp[0] = 0;
    for (int i = 0; i < n; i++)
        for (int j = coin[i]; j <= k; j++)
            dp[j] = fMin(dp[j], dp[j - coin[i]]+1);
 
    printf("%d\n", (dp[k]==INF)?-1:dp[k]);
 
    return 0;
}

 아래는 재귀함수를 이용한 top-down방식이다.  dp의 초기값을 INF로 설정하면 시간초과가 뜨고 -1로 하면 통과된다. 근데 그 둘의 차이를 모르겠다.

#include<stdio.h>
#define INF 1<<30
int dp[10100], visit[10100] = { false }, coin[110], n, k;
int fMin(int a, int b) {
    return a > b ? b : a;
}
int dpf(int a) {
    if (a < 0)    return INF;
    if (a == 0) return 0;
    if (dp[a] != -1) return dp[a];
 
    dp[a] = INF;
    for (int i = 0; i < n; i++)
        dp[a] = fMin(dp[a], dpf(a - coin[i]) + 1);
 
    return dp[a];
}
int main() {
    scanf("%d %d", &n, &k);
 
    for (int i = 1; i <= k; i++)
        dp[i] = -1;
 
    for (int i = 0; i < n; i++) {
        scanf("%d", &coin[i]);
    }
 
    dp[0] = 0;
    dpf(k);
    printf("%d\n", dp[k]==INF?-1:dp[k]);
 
    return 0;
}