(2294)(DP) 백준 동전2

https://www.acmicpc.net/problem/2294

풀이

---

첫번째 줄에 n,k를 입력한다. n은 서로 다른 값의 동전의 종류이고 그 동전들을 적당히 이용해서 그 가치의 합을 k로 만들어야할때, 동전의 개수가 최소가 될때를 구해야한다.

단, 불가능한 경우에는 -1을 출력하기로 한다.

arr[101]을 0으로 초기화해주고 

dp[100001] 을 memset(dp, -1, sizeof(dp));를 이용해서 -1로 초기화 해주기로 한다. 

dp[0]은 0 으로 초기화

동전1 문제의 풀이법을 변형해서 dp[i] = dp[i - arr[j]] + 1; 을 사용하여 동전이 사용될 때마다 +1 을 누적하여 dp에 담기로 한다.

if( i >= arr[j] && dp[i - arr[j]] != -1)의 조건을 주어서 arr[j] 동전이 i의 값을 넘지 않고 dp[i - arr[j]]이 이전의 동전들의 값으로 만들 수 있는 경우만 생각하면 된다.

하지만 dp[i] == -1 인 경우는 dp[i]가 처음으로 -1에서 값을 가지는 순간이므로 min함수로 비교를 하지않고 바로 dp[i] = dp[i - arr[j]] +1; 이 된다.  이 다음부터는

dp[i] = min(dp[i], dp[i - arr[j]] + 1);로 매번 비교를 해주어야 한다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define min(a,b) a<b ? a:b
 
int main() {
    int n, k;
    int arr[101] = { 0 };
    int dp[10001];
    
 
    memset(dp , -1, sizeof(dp));
    dp[0] = 0;
    scanf("%d %d", &n, &k);
 
    for (int i = 1; i <= n; i++) {
        scanf("%d", &arr[i]);
    }
 
    for (int i = 1; i <= k; i++) {
        for (int j = 1; j <= n; j++) {
            if (i >= arr[j] && dp[i - arr[j]] != -1) {
                if (dp[i] == -1) dp[i] = dp[i - arr[j]] + 1;
                else dp[i] = min(dp[i], dp[i - arr[j]] + 1);
            }
        }
    }
 
    printf("%d\n", dp[k]);
    
    return 0;
 
}