[프로그래머스 Level3] 거스름돈 (C++)

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

프로그래머스

문제 설명

---

Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다.

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

1원을 5개 사용해서 거슬러 준다.
1원을 3개 사용하고, 2원을 1개 사용해서 거슬러 준다.
1원을 1개 사용하고, 2원을 2개 사용해서 거슬러 준다.
5원을 1개 사용해서 거슬러 준다.
거슬러 줘야 하는 금액 n과 Finn이 현재 보유하고 있는 돈의 종류 money가 매개변수로 주어질 때, Finn이 n 원을 거슬러 줄 방법의 수를 return 하도록 solution 함수를 완성해 주세요.

 

제한 사항

---

n은 100,000 이하의 자연수입니다.
화폐 단위는 100종류 이하입니다.
모든 화폐는 무한하게 있다고 가정합니다.
정답이 커질 수 있으니, 1,000,000,007로 나눈 나머지를 return 해주세요.

 

입출력 예

---

n	money	result
5	[1,2,5]	4

 

문제 풀이

---

dp 문제.

money의 첫번째 화폐 단위로는 돈을 나타내는 j가 첫번째 화폐 단위로 나누어 떨어지면 경우의 수는 1이고, 아니면 0이다. 이를 이용해 dp 배열을 초기화해준다.

현재 탐색 중인 화폐 단위(i 반복문)를 currentMoney라는 변수에 저장할 때, 두번째 화폐 단위 이후로부터는 j원을 만드는 경우의 수를 i가 1. currentMoney보다 큰 경우, 2. currentMoney와 같을 때, 3. currentMoney보다 작을 때로 나눌 수 있다.

 

1. currentMoney보다 큰 경우

이전의 화폐 단위만 사용하는 경우와 이전의 화폐 단위와 currentMoney를 섞어서 쓰는 경우로 나눌 수 있다. 이전의 화폐 단위만 사용하는 경우는 dp[i-1][j]이다. currentMoney와 섞어서 쓴다면 j-currentMoney원을 만들 수 있는 모든 경우의 수에 currentMoney만큼을 더해 만들 수 있다. 따라서 해당 경우는 dp[i][j-currentMoney]가 된다. 두 경우를 조합하면 dp[i][j] = dp[i-1][j]+dp[i][j-currentMoney]의 식이 성립한다.

 

2.currentMoney와 같은 경우

이전의 화폐 단위만 사용하는 경우에 currentMoney만큼의 화폐 1개를 더 주면 된다. 따라서 dp[i][j]=dp[i-1][j]+1이 된다.

 

3. currentMoney보다 작은 경우

이전의 화폐 단위만 사용할 수 있다. 따라서 dp[i][j]=dp[i-1][j]가 성립한다.

 

시간 초과를 해결하기 위해 dp 배열을 2 * (money.size()+1) 크기로 선언하여 위 설명의 dp[i-1]은 dp[0]로, dp[i]는 dp[1]로 바꾸어 구현하여 dp[1][N]을 출력하였다.

 

아래는 코드.

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int solution(int n, vector<int> money) {
    int answer = 0;
    long long** dp = new long long*[2];
    for (int i=0;i<2;i++)
    {
        dp[i]=new long long[n+1];
        for (int j=0;j<n+1;j++)
        {
            dp[i][j]=0;
        }
    }
    for (int i=1;i<n+1;i++)
    {
        if (i % money.at(0) == 0)
        {
            dp[0][i] = 1;
            dp[1][i] = 1;
        }
    }
    for (int i=1;i<money.size();i++)
    {
        int currentMoney=money.at(i);
        for (int j=1;j<n+1;j++)
        {
            if (j > currentMoney)
            {
                dp[1][j] = dp[0][j] + dp[1][j-currentMoney];
                dp[1][j] %= 1000000007;
            }
            else if (j==currentMoney)
            {
                dp[1][j] = dp[0][j] + 1;
                dp[1][j] %= 1000000007;
            }
            else
            {
                dp[1][j] = dp[0][j];
            }
            dp[0][j]=dp[1][j];
        }
    }
    answer=dp[1][n];
    return answer;
}