[C++] 백준 2294: 동전 2

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

 

2293. 동전 1과 굉장히 유사한 문제이다.

다른 점은 경우의 수를 구하는 것이 아니라 사용된 동전의 개수의 최솟값을 구하는 점 정도이다.

 

 

<풀이>

풀이도 굉장히 유사한 편이다.

dp 배열의 값을 그 가치를 만드는 데 필요한 동전의 최소 개수로 지정해주면 매우 쉽게 풀 수 있다.

 

점화식은 다음과 같다

dp[j] = min(dp[j-coin[i]] + 1, dp[j]);

'원래 동전의 최소 개수'와 'i번째 코인을 사용했을 때의 개수 + 1'을 비교해서

최솟값을 넣어주는 느낌이다.

가치가 6일때를 비교해보면

1원의 동전까지만 사용했을 경우 dp배열에 6이 들어가있다.

5원의 동전까지 사용할 경우 min(dp[6-5] + 1, 6) = min(dp[1]+1, 6) = min(2, 6) = 2가 된다.

 

 

 

주의해야 할 점은 3가지 정도가 있는 것 같다.

1. 최솟값을 구하는 문제이니 만큼 초깃값을 크게 설정해줘야 한다.

#define INF 100005

for(int i = 1; i <= k; i++) dp[i] = INF;

INF의 값은 문제의 입력이 들어왔을 때 무조건 갱신될 수 있을만큼 큰 수여야 하는데

여기서는 동전의 가치가 100,000 이하이므로 100,005로 설정해줬다.

 

 

 

2. 각 동전의 가치보다 큰 값에서만 최솟값을 갱신해줘야 한다.

 if(j >= coin[i]) dp[j] = min(dp[j-coin[i]] + 1, dp[j]);

만약 이 조건이 없을경우,

j-coin[i]에서 j가 3, coin[i]가 12일 때,

3-12 = -9로

배열의 범위를 벗어나게 접근할 수 있으므로 주의하자.

 

 

 

3. 불가능한 경우에는 -1을 출력해야 한다.

문제 설명을 잘 읽지 않으면 이런 걸 놓치기 매우 쉽다.

마치 이렇게...

    if(dp[k] == INF) cout<<"-1";

이 경우 dp배열의 값이 변경되지 않음을 의미하므로 INF의 값을 가질때 -1을 출력해주면 된다.

 

 

전체 코드는 다음과 같다.

#include <iostream>
#define INF 100005
using namespace std;

int coin[105];
int dp[10005];

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

    int n, k;
    cin>>n>>k;
    for(int i = 0; i < n; i++){
        cin>>coin[i];
    }

    for(int i = 1; i <= k; i++) dp[i] = INF;

    for(int i = 0 ; i < n; i++){
        for(int j = 1; j <= k; j++){
            if(j >= coin[i]) dp[j] = min(dp[j-coin[i]] + 1, dp[j]);
        }
    }

    if(dp[k] == INF) cout<<"-1";
    else cout<<dp[k];
    return 0;
}