[Algorithm] Baekjoon 2294번 : 동전 2

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

2294번: 동전 2

 

 

 

 
 
int n, k, input;
set<int> arr;
int dp[10001] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n >> k;
 
    memset(dp, 0x3f, sizeof(dp));
 
    for (int i = 0; i < n; ++i)
    {
        cin >> input;
        if (input > k) continue;
        arr.insert(input);
    }
 
    dp[0] = 0;
    for (const int& coin : arr)
    {
        for (int i = coin; i <= k; ++i)
        {
            dp[i] = min(dp[i], 1 + dp[i - coin]);
        }
    }
 
    if (dp[k] == 0x3f3f3f3f) cout << -1;
    else cout << dp[k];
}
 

이것도 예전에 풀었던 문젠데, 그때는 당연히(?) 자력으론 못풀었었다.

이거 이전문제인 동전문제를 방금 다시 풀어봤어서, 이 문제도 다시 풀어봤다.

 

놀랍게도 풀 수 있었다. 개인적인 생각이지만, 동전문제를 풀고 이해를 했다면 이번문제도 풀 수 있을거라 생각한다.

 

비슷한 느낌으로, 작은 동전단위부터 기준으로잡고 i = 동전단위, 최대 k까지 dp테이블을 업데이트 할 것이다.

(dp테이블은 초기에 큰값으로 초기화해놓는다.)

 

dp테이블 업데이트하는 느낌은 매우 유사하다. (이전문제는 총 경우의 개수, 이번엔 최소개수를 구하는것임에도 불구하고)

기존의 dp[i]값과 1 + dp[i-coin]을 비교해서 최소값으로 업데이트한다.

여기서 1은 기준동전 1개를 사용했다는 표현이다. 그럼 자동으로 dp[i-coin]은 현재 목표값 - 기준동전1개값을 계산한 나머지 결과에 대한 dp값이다.

i가 8, 즉 현재목표값이 8이고 기준동전이 3라면, dp[8] = min(dp[8], 1 + dp[8 - 3 == 5]) 이 되는것이다.

마찬가지로 이미 dp[5]에는 이전에 3짜리 기준동전을 반영한 최소 경우의수가 포함되어있기 때문에, 이런식의 업데이트가 가능한 것이다.