동전 2 2294

문제

접근 방법

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1원	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
5원	0	1	2	3	4	1	2	3	4	5	2	3	4	5	6	3
12원	0	1	2	3	4	1	2	3	4	5	2	3	1	2	3	3

예제를 표로 그려본 것이다.
[N]=MIN([N-COIN]+1,[N])의 형태라고 볼 수 있다고 생각했다.
하지만 1원이 존재하지 않으면 불가능한 경우도 존재하기에 그러한 부분을 생각해줘야 했다.
또한 0으로 초기화된 상태에서 MIN을 사용하여 비교하면 0으로만 가득 찰 거로 생각했다.

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
5원	0	-1	-1	-1	-1	1	-1	-1	-1	-1	2	-1	-1	-1	-1	3
12원	0	-1	-1	-1	-1	1	-1	-1	-1	-1	2	-1	1	-1	-1	3

두 경우를 해결하기 위해선 가장 높은 값으로 초기화해주고 시작하면 될 것 같았다. 나올 수 없는 동전의 최소 개수는 10001이다. 10001로 초기화하고 시작하면 된다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, k;
    cin >> n >> k;
    vector<int> dp(k + 1, 10001);
    dp[0] = 0;
    while (n--)
    {
        int coin;
        cin >> coin;
        for (int i = coin; i <= k; ++i)
        {
            dp[i] = min(dp[i - coin] + 1, dp[i]);
        }
    }
    cout << ((dp[k] == 10001) ? -1 : dp[k]);
    return 0;
}

풀이

동전 1문제보다 조금 까다로워졌지만, 동전 1을 푼 사람이면 문제없이 해결할 수 있을 것이다.