[백준/C++] 2294번 동전 2

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

2294번: 동전 2

동전1과 유사한 DP문제이다.

DP는 점화식을 세우는 것이 중요한데, 이 점화식을 찾기 위해 문제의 예제를 이용해보자.

i원을 만들기 위해서 필요한 동전의 수를 dp배열에 저장할 것이다.

0원을 만들기 위해서는 동전 0개가 필요하다 -> dp[0]=0;

1원을 만들기 위해서는 1원짜리 동전 1개가 필요하다 -> dp[1]=1;

2원을 만들기 위해서는 2원짜리 동전 2개가 필요하다 -> dp[1]=2;

...

5원을 만들때를 보자!

5원을 만들기 위해서는 1원짜리 동전 5개로도 만들 수 있고, 5원짜리 동전 1개로도 만들 수 있다.

dp[5]=5; 또는 dp[5]=1; 중에서 우리는 항상 동전을 최소로 사용해야하므로 후자를 택할 것이다.

아래 코드를 보자

for (int i = 1; i <= k; i++){
        for(int j=1; j<=n;j++){
            if(i < coin[j]) continue;

            int tmp = dp[i-coin[j]] + 1;
            if(tmp < dp[i]) dp[i] = tmp;
        }
    }

dp[i-coin[j]]가 의미하는 것은 무엇이냐, i원을 만들 때 어떤 동전을 이용해 대체할 수 있으면 (예를 들면 위에 dp[5]같은 느낌) 대체하라는 것이다. +1은 현재 동전을 사용했음을 count해주기 위한 것!

​

5원을 다시 예로 들어보자.

dp[5-coin[j]]에서 coin[j]에는 차례로 1,5가 들어올 것이다. (12는 if문에 걸려서 안옴) (음수 인덱스는 에러를 유발하기 때문)

그럼 tmp는 coin[1](=1)일 때 5라는 수를 가지고, coin[2](=5)일 때 1이라는 값을 가질 것이다. 결국 dp[5]에는 최솟값인 1이 저장!

=> dp[i]는 i원을 만들기 위해 사용한 동전의 최소 숫자를 저장하는 배열이다!

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int n,k;
int coin[101];
int dp[10001];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >>k;
    for (int i = 1; i <= n; i++)
        cin >> coin[i];

    for(int i=1; i<=k;i++) {
        dp[i] = 987654321;
    }
    dp[0]=0;
    for (int i = 1; i <= k; i++){
        for(int j=1; j<=n;j++){
            if(i < coin[j]) continue;

            int tmp = dp[i-coin[j]] + 1;
            if(tmp < dp[i]) dp[i] = tmp;
        }
    }
    if(dp[k] >= 987654321) dp[k] = -1;
    cout << dp[k];

    return 0;
}