[programmers] 거스름돈

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

프로그래머스

 

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

dp

 

---------------------------------------------------풀이----------------------------------------------------

 

methods[n]을 n원을 거슬러줄 수 있는 방법의 가짓수라고 하자.

그럼 처음 methods[] 배열은 0으로 초기화되어 있을 것이다.

그 뒤에, dp를 적용하였다.

여기서의 점화식은 다음과 같다.

 

거스름돈을 n원, 화폐 단위를 m이라고 할 때, 

methods[n] += methods[n-m1] + methods[n-m2] + methods[n-m3] + ...

                       = sum(methods[n-m]) for all m

이다.

즉, n원을 거슬러주는 방법의 가짓수는 모든 m에 대해 (n-m)원을 거슬러주는 가짓수의 합과 같다.

 

다음과 같이 생각해보자.

n이 5일 때, m이 1, 2, 5라고 하자.

먼저, 5원을 주기 위해서는 다음과 같은 세 가지 방법이 있다.

1. 4원(n-m1)을 주고 1원(m1)을 주기 = methods[n-m1] = methods[4]

2. 3원(n-m2)을 주고 2원(m2)을 주기 = methods[n-m2] = methods[3]

3. 0원(n-m3)을 주고 5원(m3)을 주기 = methods[n-m3] = methods[0]

m원만큼 주는 것은 한 가지 경우의 수로 보기 때문에, 앞에 있는 n-m에 대한 가짓수만 신경쓰면 된다.

따라서 methods[5] += methods[4] + methods[3] + methods[0]이 되고,

methods[4]와 methods[3], methods[0] 에 대해서도 위와 같은 방식으로 n이 달라졌다고 생각하고 계산하면 된다.

#include <string>
#include <vector>
#include <iostream>

using namespace std;

// methods[n] = n 원을 거슬러줄 수 있는 방법의 가짓수
int methods[100'001] = {0, };

// 거스름돈을 n원 줄 때 방법의 경우의 수 = ?
// 1 <= n <= 100'000, money 종류 100종류 이하. 각 개수는 무한.
int solution(int n, vector<int> money) {
    // dp
    for(int i = 0; i < money.size(); i++){
        int m = money[i];
        methods[m]++;
        // m이 m이후의 수에 사용되는 경우
        // dp[n] = n을 만드는 가짓수
        // = sum for all m(dp[n] + dp[n-m]) = 모든 화폐 단위 m에 대해, m을 한 번 사용했을 경우의 가짓수의 합
        for(int j = m+1; j <= n; j++){
            int cur = j - m;
            methods[j] = (methods[j] + methods[cur]) % 1'000'000'007;
        }
    }
    return methods[n] % 1'000'000'007;
}

 

---------------------------------------------------후기----------------------------------------------------

 

dp는 뭔가 항상..이런거 같은데?오 맞아! 라는 느낌으로 풀리는중

1'000'000'007로 나누라는 것을 보자마자 dp가 떠올랐다.

그렇게 큰 수를 계산하는 문제라면 dfs는 아닐 거라는거~!