프로그래머스 문제 - 거스름돈

프로그래머스 거스름돈 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

Finn은 손님에게 거스름돈을 n원 거슬러주어야 합니다.
거스름돈으로 줄 수 있는 돈의 종류 money가 주어집니다.
돈은 각각 무한하게 있다고 가정합니다.
거슬러 줄 수 있는 방법의 수를 구해야합니다.

문제 풀이

알고리즘 문제 중에서 꼭 보이는 동전 문제입니다.
제한 사항이 적다면 dfs나 bfs로 해결이 가능하지만 n은 100000이고 화폐 단위도 100개 이하이므로 문제를 풀 수 있는 점화식을 찾아야 합니다.
이번 문제는 배열을 사용하여 문제를 풀어보았습니다.

배열의 인덱스는 손님에게 드려야 할 거스름돈의 양이라 생각해줍니다
거스름돈이 0원인 경우에는 아무것도 드리지 않으면 되기 때문에 arr[0]은 1로 해줍니다.
이후 돈의 종류를 sort하여 오름차순으로 정렬 후 제일 작은 수의 동전을 먼저 찾아 더해주도록 합니다.

예시 문제처럼 1, 2, 5의 money가 주어지고 n=5의 값을 찾아보겠습니다.

1원을 가지고 거스름돈을 줄 수 있는 값 찾기
거스름돈이 1원일 경우 현재까지 준 거스름돈이 0인 상태에서 1만 주면 되기 때문에 arr[1] = arr[1]+arr[0]
거스름돈이 2원일 경우 현재까지 준 거스름돈이 1인 상태에서 1만 주면 되기 때문에 arr[2] = arr[2]+arr[1]
거스름돈이 3원일 경우 현재까지 준 거스름돈이 2인 상태에서 1만 주면 되기 때문에 arr[3] = arr[3]+arr[2]
거스름돈이 4원일 경우 현재까지 준 거스름돈이 3인 상태에서 1만 주면 되기 때문에 arr[4] = arr[4]+arr[3]
거스름돈이 4원일 경우 현재까지 준 거스름돈이 4인 상태에서 1만 주면 되기 때문에 arr[5] = arr[5]+arr[4]

이런 식으로 1원을 가지고 줄 수 있는 가짓수를 구할 수 있습니다.
이런식으로 2원으로 줄 수 있는 가짓수도 구해줍니다.

1원을 가지고 거스름돈을 줄 수 있는 값 찾기
거스름돈이 2원일 경우 현재까지 준 거스름돈이 0인 상태에서 2만 주면 되기 때문에 arr[2] = arr[2]+arr[0]
거스름돈이 3원일 경우 현재까지 준 거스름돈이 1인 상태에서 2만 주면 되기 때문에 arr[3] = arr[3]+arr[1]
거스름돈이 4원일 경우 현재까지 준 거스름돈이 2인 상태에서 2만 주면 되기 때문에 arr[4] = arr[4]+arr[2]
거스름돈이 5원일 경우 현재까지 준 거스름돈이 3인 상태에서 2만 주면 되기 때문에 arr[5] = arr[5]+arr[3]

이렇게 money의 값들을 전부 찾아내게 된다면 arr[n]값이 정답이 됩니다.
그래서 점화식은

arr[i] = arr[i] + arr[i-현재 거스름돈 값]

전체 코드

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> money) {
    int answer = 0;
    long long arr[100001] = {0,};
    
    sort(money.begin(), money.end());
    arr[0] = 1;
    for(int i = 0; i < money.size(); i++)
    {
        int cur = money[i];
        for(int j = cur; j <= n; j++)
        {
            arr[j] = arr[j] + arr[j - cur];
        }
    }
    
    answer = arr[n] % 1000000007;
    
    return answer;
}

출처

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