(JAVA) 거스름돈

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12907

프로그래머스

풀이

처음에 이 문제를 딱 보았을 때는 DFS로 풀면 되지 않나라는 생각을 가지고 코드를 빠르게 작성했다. 작성 후에 테스트 케이스들도 무난하게 통과하고, 나름대로 엣지 케이스들도 추가하여 테스트를 진행했는데 모두 잘 통과해서 기분 좋게 제출을 하였지만 역시나 한번에 통과할 수 없었다. 필자가 푼 방법으로는 money 배열에 중복된 값이 들어오는 경우에는 실패하는 코드였고, 만약 올바른 알고리즘이었더라도 1000000007로 나누라는 문제의 조건을 봤을 때 하나씩 모두 탐색하는 DFS의 경우에는 시간 초과가 발생할 가능성이 너무나도 높아보였다.

 

그래서 DFS가 아닌 다른 알고리즘인 DP로 이 문제를 해결하도록 노력해보았다. 그런데 항상 DP는 코드는 복잡하지 않은데 해결 방법을 생각하는 과정이 너무나 어려웠다. 그래서 해결 방법을 생각하기 위해 먼저 엑셀에 아래와 같은 표를 작성해보았다.

	1	2	3	4	5	6	7
1	1	1	1	1	1	1	1
1,2	1	2	2	3	3	4	4
1,2,5	1	2	2	3	4	5	6

이 표를 유심히 들여다보면 뭔가 규칙을 찾을 수 있다. 하지만 당연히 한 번에 파악하기엔 너무나도 어려울 것이다.

숫자가 변하는 부분에서의 규칙을 찾아봐보자. 겨우 이 정도의 힌트에서 규칙을 발견할 수는 없을 것이라고 본다.

 

이제 좀 더 자세하게 설명해보겠다. 문제에서 예시로 들은 경우가 1,2,5를 모두 사용해서 5를 만드는 경우의 수를 구하는 것이었다. 이 경우 나올 수 있는 조합은 1,1,1,1,1 / 1,1,1,2 / 1,2,2 / 5 이렇게 4개이다. 이 조합은 당연하게도 1로 5를 만들 수 있는 조합의 수 + 1과 2로 5를 만들 수 있는 조합의 수 + 1,2,5를 사용하여 만들 수 있는 조합의 수이다.

이 문제는 DP 문제이기 때문에 이전의 결과값을 저장해두었다가 다시 사용할 수 있다는 점을 고려하면 1과 2로 n을 만들 수 있는 조합의 수에서는 1로 n을 만들 수 있는 조합의 수를 사용할 수 있고, 마찬가지로 1, 2, 5로 n을 만들 수 있는 조합의 수에서는 1과 2로 n을 만들 수 있는 조합을 사용할 수 있다.

그렇기에 이전에 저장해둔 값을 사용한다면

(1, 2, 5로 n을 만들 수 있는 조합의 수) =  (1과 2로 n을 만들 수 있는 조합의 수) + (5를 사용하기 위해 1과 2로 n-5를 만들 수 있는 조합의 수)

위와 같은 점화식을 도출해낼 수 있다.  

 

위의 점화식을 검증하기 위해 예를 들어 1, 2, 5로 7을 만든다고 하자. 그럼 위의 점화식에 따르면 1과 2로 7을 만들 수 있는 조합의 수와 5를 사용하기 위해 1과 2로 2(7-5)를 만드는 조합의 수의 합이 되는 것이다. 이를 계산하면 4 + 2 = 6이다.

실제로 조합을 나열해보면 아래와 같이 6개이므로 위의 점화식은 옮음을 알 수 있다.

1,1,1,1,1,1,1 / 1,1,1,1,1,2 / 1,1,1,2,2 / 1,2,2,2 / 1,1,5 / 2,5

 

마지막으로 실제 코드를 보자.

import java.util.*;

class Solution {
    public int solution(int n, int[] money) {
        long[] answer = new long[100001]; // money로 만들 수 있는 n일 때의 조합의 수를 저장할 배열
        // 1,2,5로 5를 만들 때와 같이 1,2로 5를 만드는 경우와 1,2로 5-5를 만드는 경우를 생각하였을 때 answer[0]은 1이어야 함
        answer[0] = 1;
        for (int m : money){ // 1,2,5의 순서대로
            for (int i = m; i <= n; i++){ // n을 만드는 조합의 수를 채우기
                answer[i] += answer[i-m];  // 이전에 나타난 숫자들로 만드는 조합의 수와 현재 수를 뺀 값을 만드는 조합의 수를 합산
            }
        }
           
        return (int) (answer[n] % 1000000007); // 나머지를 int로 형변환
    }
}