문제

백준 2294

코드

#include <bits/stdc++.h>

using namespace std;

int n, k;
vector<int> coin;
int dp[10004];

int main()
{
    cin >> n >> k;

    for (int i = 0; i < n; i++)
    {
        int input; cin >> input;
        coin.push_back(input);
    }

    fill(dp, dp + 10004, INT_MAX);
    dp[0] = 0;

    for (int i = 0; i < n; i++)
    {
        if (coin[i] > 10000) continue;

        dp[coin[i]] = 1;

        for (int j = coin[i]; j <= 10000; j++)
        {
            if (dp[j - coin[i]] == INT_MAX) continue;

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

    if (dp[k] == INT_MAX)
        cout << -1;
    else
        cout << dp[k];
    

    return 0;
}
 

풀이

DP를 오랜만에 푸니까 정말 반갑다

내가 선택한 방식은 일단 쓸 수 있는 동전을 받아둔다

그리고 dp[i]는 i원을 만들 수 있는 최소 동전 개수로 둔다

최소를 구하니까 초기화는 INT_MAX로 시키고 혹시 몰라 dp[0]은 0으로 초기화 시켜둠(0원 만들려면 0개 필요하니까~)

반복문은 동전 하나 하나를 순회하며 dp 배열을 초기화시켜주는 것임

최대 동전 개수는 100개이고 최대 10000원까지 만드는 것이니까 시간 복잡도는 O(100*10000 = 1,000,000)이라 1초 안에 가능하다

그리고 동전이 10,000원보다 크면 의미가 없으므로 바로 넘어가주자

처음 dp[동전 가치]를 1로 초기화 시켜준다. 5원 동전이 있을 때 5원을 만드는 방법은 동전 1개이기 때문에

그리고 동전 가치부터 반복문을 시작해 10000원까지 1원씩 증가시켜간다

점화식은 dp[j] = min(dp[j], dp[j - coin[i]] + 1)인데 예를 들어 6원을 만들어야 하는데 동전이 1원, 5원이 있다고 하면 1원만 쓸때는 6원을 만들려면 6개를 써야한다

1원만 쓸 때 6원을 만들려면 5원에서 동전 1원을 1개만 더 쓰면 된다

그리고 동전 5원을 기준으로 하면 6원을 만들려면 1원에서 5원짜리 1개를 쓰면 된다

즉 j원에서 현재 동전 가치만큼 뺀거에 1을 더한 것과 기존의 j원과 비교해서 더 작은 값을 채택한다

이때 dp[j - coin[i]]이 INT_MAX라는 말은 그렇게 만들 수 없다는 것이니까 패스시키면 됨

그리고 마지막으로 dp[k]를 출력하면 되는 문제임