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

27 Oct 2023 in Study on Coding Test

오히려 동전 1 보다 뭔가 더 익숙했던 DP 문제

정답제출코드

#include <iostream>
#include <set>

using namespace std;

int m_min(int a, int b)
{
    if (a < b)
        return a;
    else
        return b;
}

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

    int N, K;
    int DP[10001];

    for (int i = 0; i <= 10000; ++i)
        DP[i] = 10001;
    
    set<int> Coin;

    cin >> N >> K;

    for (int i = 0; i < N; ++i)
    {
        int _input;
        cin >> _input;
        Coin.insert(_input);
    }
    
    DP[0] = 0;
    for (auto iter = Coin.begin(); iter != Coin.end(); ++iter)
    {
        for (int j = *iter; j <= K; ++j)
            DP[j] = m_min(DP[j], DP[j - *iter] + 1);
    }

    if (DP[K] == 10001)
        cout << -1;
    else
        cout << DP[K];

    return 0;
}

이번 문제는 동전 1과 차이점은

1. 같은 동전이 여러개 주어질 수 있다.
2. 최소 개수를 구하는 것이다.

1번 조건이 붙어 있어서 이번에는 vector대신 set을 사용하였다.

중복되면 오히려 헷갈리니까..

set은 중복을 없애주는 대신에, for문으로 순회하기 위해서는 iter를 사용해야한다는 점 알아두자.

그리고 2번 조건이 붙어있기 때문에 m_min함수를 만들어주었다.

사실, algorithm 헤더를 include하고 min을 써줘도 되긴 하지만 난 이게 익숙해서..

DP[0] = 0을 제외하고 나머지 DP 배열 값을 10001로 저장을 해둔 다음,

동전 개수를 세주며 갱신할 수 있으면 갱신하는 식으로 구현하였다.