[백준] 2293_동전 C++

26 Oct 2023 in Study on Coding Test

살짝쿵 헷갈렸던 DP문제

정답제출코드

#include <iostream>
#include <vector>

using namespace std;

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

    int N, K;
    int DP[10001] = {0};
    vector<int> Coin;

    cin >> N >> K;

    Coin.resize(N);

    for (int i = 0; i < N; ++i)
        cin >> Coin[i];
    
    DP[0] = 1;
    for (int i = 0; i < N; ++i)
    {
        for (int j = Coin[i]; j <= K; ++j)
            DP[j] = DP[j] + DP[j - Coin[i]];
    }

    cout << DP[K];

    return 0;
}

문제에서 경우의 수를 구하고, 제한 시간이 0.5초인 것을 보고 DP임을 직감했다.

이번 문제의 가장 큰 관건은 K의 값을 나타내는 경우의 수를 구하는 것이었다.

DP[0] = 1을 설정할 생각을 하지 못하고 있었다가 구글링을 통해서 방법을 찾아내었다.

이를 해주어야 하는 이유는 DP[Coin[i]]의 경우의 수를 나타내면서 for문을 한 가지로만 쓸 수 있도록

하기 위해서일 것이다.

예를 들어, Coin[i]가 3이라고 했을 때

DP[0] = 1;
for (int i = 0; i < N; ++i)
{
    for (int j = Coin[i]; j <= K; ++j)
        DP[j] = DP[j] + DP[j - Coin[i]];
}

DP[3] = 0 + DP[3 - 3] (= DP[0] = 1)

이렇게 되니까 DP[3]은 자동으로 1가지가 된다. 실제로, 한 가지이기도 하고.

이렇게 한 다음에 다른 동전으로 계산한 경우도 더하게 되어 자동으로 DP에 동전으로 나타내는 경우의 수가 저장된다.

그러고 나서 K의 경우의 수를 출력하면 된다.