2294 동전 2

2294. 동전 2 / c++ / Gold5 / 40분

문제

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

1. 동전 N개와 금액 K가 주어진다. (동전 종류에 중복 있음)
2. K개를 만들 수 있는 최소한의 동전의 갯수는? (못만들 경우 -1)

접근 방식

동적 프로그래밍

1. 동전을 set에 저장 (중복 제거 / 오름차순 정렬)
2. DP(K) 실행
   1. dp[K]가 0이 아니면 출력
   2. 0이면
      1. 동전 종류 iter 중 가격이 큰 것부터 DP(iter) + DP(K - iter)
      2. 만약 만들 수 없다면 -1
      3. 만들 수 있다면 그 값중 가장 최소값을 dp[K]에 입력

문제 풀이

#pragma GCC optimize("Ofast")
#include <iostream>
#include <set>
#define MAX_CNT 987'654'321
using namespace std;
inline int MIN(int A, int B) { return A < B ? A : B; }
int N, K, coin;

int dp[10'001] = {};
set<int> coins;

int DP(int price)
{
    if (price == 0) return 0;
    if (dp[price] == 0)
    {
        int minCnt = MAX_CNT;
        for (auto iter = coins.rbegin(); iter != coins.rend(); ++iter)
        {
            if (*iter <= price)
            {
                int cnt1 = DP(*iter);
                int cnt2 = DP(price - *iter);
                if (cnt1 == -1 || cnt2 == -1) continue;
                minCnt = MIN(minCnt, cnt1 + cnt2);
            }
        }

        dp[price] = minCnt == MAX_CNT ? -1 : minCnt;
    }

    return dp[price];
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> N >> K;

    for (int i = 0; i < N; ++i)
    {
        cin >> coin;
        if (coin > 10'000) continue;
        coins.insert(coin);
        dp[coin] = 1;
    }

    cout << DP(K) << '\n';

    return 0;
}

다시 생각해 볼 점

1. 이번 DP는 dp[i] = dp[j] + dp[k] 순이었다.
2. 가격을 1 ~ K /2 까지 구분하면 에러가 났다.
3. 결국 동전의 가치를 기준으로 계산해야했기에, set coins를 역순으로 돌면서 DP를 돌렸더니 해결됐다.
4. DP 내부 기준을 동전의 가치 set으로 설정한게 중요했다.