[프로그래머스 Programmers] 거스름돈

문제 설명

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 해주세요.

 

프로그래머스

 

 

실패한 풀이 코드(중복 조합으로 작성)

#include <string>
#include <vector>

using namespace std;

void combination(vector<int> arr, int r, int index, int depth, long* count)
{
    if (r == 0)
    {
        (*count)++;
        return;
    }
    else if (depth == arr.size())
    {
        return;
    }
    else
    {
        if (r - arr[depth] < 0) return;

        combination(arr, r - arr[depth], index + 1, depth, count);
        combination(arr, r, index, depth + 1, count);
    }
}

int solution(int n, vector<int> money) {
    
    long count = 0;
    combination(money, n, 0, 0, &count);
    return count % 1000000007;
}

 

 

DP로 풀어야한다는 힌트만 얻은 상태로 종료

 

성공한 풀이 코드(DP로 작성)

#include <string>
#include <vector>

using namespace std;

int combination(int n, vector<int> money)
{
    vector<int>dp(n + 1, 0);

    dp[0] = 1;

    for (int i = 0;i < money.size();i++) {
        for (int j = 1;j < n + 1;j++) {

            if (j >= money[i]) 
            {
                dp[j] += dp[j - money[i]];
            }
            else 
            {
                continue;
            }
        }
    }

    return dp[n];
}

int solution(int n, vector<int> money) {
    
    int count = combination(n, money);
    return count;
}

 

해당 경우의 수를 엑셀로 정리

해당 경우의 수를 엑셀로 정리해봤다.

money가 1인 경우

j - 1이기 때문에 바로 옆칸의 값을 더해준다.

dp[1] += dp[1 - money[0]] == dp[1] += dp[0]

dp[2] += dp[2 - money[0]] == dp[2] += dp[1]

 

money가 2인 경우

j - 2이기 때문에 바로 옆옆칸의 값을 더해준다.

dp[2] += dp[2 - money[1]] == dp[2] += dp[0]

dp[4] += dp[4 - money[1]] == dp[4] += dp[2]

money가 5인 경우

j - 5이기 때문에 바로 옆옆옆옆옆칸의 값을 더해준다.

dp[5] += dp[5 - money[2]] == dp[5] += dp[0]

dp[7] += dp[7 - money[2]] == dp[7] += dp[2]

 

이해가 잘 안되었는데 엑셀로 정리해서 함수로 만들어보니 이해도가 살짝 상승하였다.

 

DP.xlsx

0.01MB

 

참조 사이트

[프로그래머스] 거스름돈 / Java