Programmers - 거스름돈

---

title: Programmers - 거스름돈
date: 2022-10-03
tags:

• Algorithm
• DP

---

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

문제 요약

주어진 돈의 단위를 이용하여 n원을 만들어야 한다.
각 돈의 개수는 무한하며, 중복되는 조합 없이 만들 수 있는 조합의 수 % 1,000,000,007을 return한다.

문제 풀이

처음에는 O(n * money의 개수) 방식으로 문제를 해결하고자 하였다.
각 값에서 Unit을 뺀 값을 더해주는 방식으로 DP 알고리즘을 작성하였다.
이 방식의 문제는 간단하다. 1,2라는 Unit이 있을 경우, x원을 만들 때 (x-3,2,3) , (x-3,3,2) 라는 중복 조합이 발생하여도 개수가 더해진다.
이를 해결하려면 현재 단위를 기준으로 다른 모든 단위와의 최소공배수에 해당하는 값을 구한 후, DP [ 현재 값 - 구한 값 ] 을 빼주어야 한다.
복잡한 알고리즘이 되며, 중복하여 빼게 되는 경우를 판별하는 알고리즘이 추가적으로 필요하다.
간단한 문제에 과한 알고리즘이 도입되는 것이라 판단하였으며, 발상을 약간 바꾸어 해결하였다.


동일하게 O(n * money의 개수) 방식의 풀이이다.
이전 풀이의 for loop은 값 1씩 증가 -> 모든 Unit에 대한 DP 합 처리이다.
중복 조합이 발생하는 것은 (2,3) 과 (3,2)가 동시에 처리되기 때문에 발생한 문제이다.
Unit 처리 순서를 정해주면 이러한 문제를 피할 수 있다.
for loop을 모든 Unit -> 값을 더해주며 DP 합 처리로 바꾸면 해결 가능하다.
이전 Unit들을 이용한 모든 조합에서 현재 Unit에 대한 경우의 수만 더해주는 방식이다.
Unit 처리 순서를 정해주었기에 중복 조합이 발생하지 않는다.
CPU의 Modulo 연산은 다른 연산보다 시간이 오래 걸리기에 마지막에 한 번만 Modulo 처리를 해주어 조금 더 많은 Memory를 사용하여 CPU 속도를 개선하였다.

프로그램

#include <vector>
#include <algorithm>

using std :: vector ;

int solution ( int n , vector < int > money )
{
    int answer = 0 ;
    vector < long long > vDP ( n + 1 , 0 ) ;
    int iMoneySize = money.size () ;



    vDP [ 0 ] = 1 ;
    for ( int i = 0 ; i < iMoneySize ; ++i )
    {
        int iMoney = money [ i ] ;

        for ( int j = iMoney ; j <= n ; ++j )
        {
            vDP [ j ] += vDP [ j - iMoney ] ;
        }
    }


    return vDP [ n ] % 1000000007 ;
}