[Algorithm] Programmers :: 거스름돈

https://school.programmers.co.kr/learn/courses/30/lessons/12907

프로그래머스

int dp[100001];
 
int solution(int n, vector<int> money) {
    int answer = 0;
 
    dp[0] = 1;
 
    for (int i = 0; i < money.size(); ++i)
    {
        int inputMoney = money[i];
 
        for (int j = inputMoney; j <= n; ++j)
        {
            dp[j] = dp[j] + dp[j - inputMoney] % 1000000007;
        }
    }
 
    return dp[n];
}

 

이 문제는 아직 풀지 못했다.

dp[j - inputMoney]의 정의를 제대로 해석해서 이해를 못했다. 우항의 dp[j]같은 경우는 이전 동전단위까지를 사용했을때 j를 만들 수 있는 경우의수..라고 생각하는데... 그 뒤를 풀이하지 못하겠다.

나중에 풀든, 어쩌든 일단 시간을 너무 써서 흔적만 남겨둔다.