프로그래머스 Lv3 거스름돈

---

접근법

"정답이 커질 수 있으니, 1,000,000,007로 나눈 나머지를 return 해주세요." 라는 문구를 보고 완전 탐색은 배제해야하는 문제이다.

 

따라서 DP로 접근해야하는데,

 

예를 들어서 손님께 5원을 거슬러 줘야하고 1원, 2원, 5원이 있다면 다음과 같이 4가지 방법으로 5원을 거슬러 줄 수 있습니다. 1원은 5개를 사용해서 거슬러 준다. 1원을 3개 사용하고, 2원을 1개 사용해서 거슬러 준다. 1원을 1개 사용하고, 2원을 2개 사용해서 거슬러준다. 5원을 1개 사용해서 거슬러준다.

 

예시를 보고 3원을 구하는 경우의 수를 볼 때 3원 = 1원 + 1원 + 1원3원 = 1원 + 2원3원 = 2원 + 1원이렇게 경우의 수가 순서에 따라 달라질 수 있으므로 순서에도 신경을 써야하는 문제이다. 정답은 2가지이다.

 

점화식을 구해보자면

---

coin이 1일 때

D[1] += D[0] (1가지)

D[2] += D[1] (1가지)

D[3] += D[2] (1가지)

D[4] += D[3] (1가지)

D[5] += D[4] (1가지)

 

coin이 2일 때

D[2] += D[0] (2가지)

D[3] += D[1]  (2가지)

D[4] += D[2]  (2가지)

D[5] += D[3]  (3가지)

 

coin이 5일 때

D[5] += D[0] (4가지)

 

즉 점화식은 D[m] = sum(D[m- coin]) 이 된다. ( 1 <= m <= N, coin은 문제에서 주어진 동전의 단위

 

이를 코드로 나타내면

for(coin : conins)
{
	for(int i = coin; i <= n; ++i)
    {
    	DP[i] += DP[i - coin];
    }
	
}

---

전체 코드

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> money) {
    int answer = 0;
    vector<int> DP = vector<int>(n + 1, 0);
    DP[0] = 1;
    
    for(auto coin : money)
    {
        for(int i = coin; i <= n; ++i)
        {
            DP[i] += DP[i - coin] % 1'000'000'007;
        }
    }
    return DP[n];
}