Level 3. 거스름돈

Level 3. 거스름돈

 

 

문제를 읽고 왠지 DP일 것 같은 느낌이 들었다.

 

이제 좀 감을 잡았나 보다..

 

화폐 단위를 정렬하고 작은 화폐 단위부터 DP를 진행하는 이유는 중복을 처리하기 위함이다.

• [1, 2, 2]와 [2, 2, 1]은 같은 것이기 때문에 작은 것부터 수행해야 한다.
• for문에 금액이 먼저 오게되면, 중복 처리가 매우 번거로워진다.

 

DP도 무작정 하는 것이 아니라, 중복을 고려해 때에 따라 정렬과 for문의 순서를 조정해야 한다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int n, vector<int> money)
{
    int DIV = 1'000'000'007;
    vector<int> DP(n + 1, 0);

    DP[0] = 1;
    sort(money.begin(), money.end());

    for (int mny : money)
        for (int i = 0; i <= n - mny; ++i)
            DP[i + mny] = (DP[i] + DP[i + mny]) % DIV;

    return DP[n];
}