C++ / 프로그래머스 / 거스름돈

문제

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

프로그래머스

 

문제풀이

이전에 풀었던 백준 문제와 똑같다.

동적 계획법인 dp를 이용해 풀었다.

동전의 구성은 같지만, 순서만 바꿔서 다른 경우는 같은 경우로 친다.

DP[n] = DP[n-원]이 기본 형태이다.

1원은 1원 동전으로 만들 수 있다.

2원은 1원의 경우의 수와 같다.

3원은 1원의 경우의 수와 같다.

 

.

2원은 기존 방법에서 추가로 더한다.

2원은 2원의 동전으로 만들 수 있다. 1+1

3원은 1원의 경우의 수를 추가로 더한다. 1+1

5원은 3원의 경우의 수를 추가로 더한다. 1+(1+1) / 동전 (1, 1, 1, 1, 1), (1, 1, 1, 2), (1, 2, 2)

 

 

 

위 표는 1, 2, 5원으로 6원을 만드는 개수를 구하는 과정이 담긴 표다.

이런 식으로 사용할 수 있는 동전부터 시작하여 이전의 값을 이용하여 구한다.

그리고 덧셈을 할 때는 제한 사항에 나와있는 값으로 항상 나눈 나머지로 저장해야 한다.

 

코드

#include <string>
#include <vector>
#define DIV 1000000007
using namespace std;

int solution(int n, vector<int> money) {
    int idx(0), won(0);
    vector<int>cnt(n + 1, 0);

    cnt[0] = 1;

    for (won = 0; won < money.size(); ++won) {
        for (idx = money[won]; idx <= n; ++idx) {
            cnt[idx] += (cnt[idx - money[won]] % DIV);
        }
    }

    return cnt[n];
}