(javascript) 거스름돈

코딩테스트 연습 - 거스름돈 | 프로그래머스 스쿨

프로그래머스

 

재귀함수 및 동적 프로그래밍으로 푸는 문제... 인줄 알았는데 아니었다.

 

처음에는 익숙한 재귀함수 방법으로 접근했다.

 

예제의 문제를 보면, solution(5, [1, 2, 5])를 풀 때, 다음과 같은 재귀적 접근 방법을 생각해볼 수 있다.

5원을 거슬러주는 방법을 구하려면,

1. 먼저 1원을 거슬러 주고 나머지 4원을 거슬러주는 방법

2. 먼저 2원을 거슬러 주고 나머지 3원을 거슬러주는 방법

3. 먼저 5원을 거슬러 주고 나머지 0원을 거슬러주는 방법

(1), (2), (3)의 값을 모두 더하면 최종적으로 5원을 거슬러주는 방법의 수가 나올 것이다.

 

그러나 실제로 위 방법을 적용해보면 예상과는 다른 답이 나온다.

위 방법을 점화식으로 표현해보면 아래와 같다.

f(0) = 1,
f(x) = 0 (x < 0),
f(n) = f(n-1) + f(n-2) + f(n-5)

이 때 n = 0부터 5까지의 값을 직접 구해보면

f(0) = 1
f(1) = f(0) + f(-1) + f(-4) = 1 + 0 + 0 = 1
f(2) = f(1) + f(0) + f(-3) = 1 + 1 + 0 = 2
f(3) = f(2) + f(1) + f(-2) = 2 + 1 + 0 = 3
f(4) = f(3) + f(2) + f(-1) = 3 + 2 + 0 = 5
f(5) = f(4) + f(3) + f(0) = 5 + 3 + 1 = 9

그러나 실제로 5원을 거슬러주는 방법은

1 1 1 1 1
1 1 1 2
1 2 2
5

4가지 방법밖에 없다.

 

왜 이런 문제가 발생하냐면 거스름돈에는 순서가 없기 때문이다.

예를 들어 3원을 거슬러준다고 할 때, 1원을 먼저 주고 2원을 주는것과 2원을 먼저 주고 1원을 주는것에는 차이가 없다는 것이다.

 

따라서 계산할 때 중복되는 경우의 수를 제거해야한다.

---

그래서 방법을 바꿨다.

새로운 방법은 말로 설명하기 어렵다.

한마디로 하자면 동전을 한 종류씩 추가해가며 경우의 수를 누적시킨다고 할 수 있다.

 

예를 들어 1, 2, 5원짜리 동전으로 5원을 거슬러준다고 생각해보자.

먼저 거슬러줄 수 있는 동전이 하나도 없는 경우, 거스름돈이 0원인 경우를 제외하면 방법이 없다.

 

동전이 한 종류도 없을 때, n원을 거슬러 주는 방법을 k(n)이라고 한다면,

n = 0일 때 k(n) = 1, n != 0일 때 k(n) = 0이다.

 

이제 1원짜리 동전을 추가해준다.

n원을 거슬러주고 싶다면 두가지 방법이 있다.

1원짜리 동전을 하나도 사용하지 않고 n원을 거슬러 주는 방법과, 1원짜리 동전을 하나 이상 사용해서 n원을 거슬러 주는 방법이다.

두 경우의 수를 더하면 1원짜리 동전으로 n원을 거슬러 주는 경우의 수를 구할 수 있다.

 

1원짜리 동전을 하나도 사용하지 않고 n원을 거슬러 주는 방법은 이미 알고있다. (k(n))

1원짜리 동전을 사용해서 n원을 거슬러주는 경우의 수를 f(n)이라고 한다면, 1원짜리 동전을 하나 이상 사용해서 n원을 거슬러 주는 방법은 f(n-1)을 먼저 거슬러준 뒤 1원짜리 동전을 하나 거슬러주는 것과 같다.

그러면 f(n-1)에 1원짜리 동전을 사용했는지 사용하지 않았는지 알 수 없지만 반드시 1원짜리 동전을 하나 사용하게 된다.

즉, f(n) = 0 (n<0),

               k(n) + f(n-1) (n>0)

이라고 할 수 있다.

 

우리는 f(5)의 값을 구하고 싶다.

f(5)
= k(5) + f(4)
= ...
= k(5) + k(4) + k(3) + k(2) + k(1) + f(0)
= 1

이므로, f(0) ... f(5)은 모두 1이 된다.

f(0)	f(1)	f(2)	f(3)	f(4)	f(5)
1	1	1	1	1	1

 

이제 2원짜리 동전을 추가한다.

그러면 n원을 거슬러줄 때 두가지 방법이 있다

2원짜리 동전을 하나도 사용하지 않고 n원을 거슬러 주는 방법과, 2원짜리 동전을 하나 이상 사용해서 n원을 거슬러 주는 방법이다.

 

우리는 이미 2원짜리 동전을 하나도 사용하지 않고 n원을 거슬러주는 경우의 수를 알고있다. (f(n))

 

1원과 2원짜리 동전으로 n원을 거슬러주는 경우의 수를 g(n)이라고 할 때,

g(n) = 0 (n<0),

           f(n) + g(n-2) (n>0)

이라고 할 수 있다.

 

따라서

g(5)
= f(5) + g(3)
= f(5) + f(3) + g(1)
= f(5) + f(3) + f(1) + g(-1)
= 3

이다.

 

n=0부터 5까지 g(n)의 값을 구해보면 다음과 같다.

g(0)	g(1)	g(2)	g(3)	g(4)	g(5)
1	1	2	2	3	3

 

이제 5원짜리 동전을 추가해보자.

1, 2, 5원짜리 동전을 사용해서 n원을 거슬러줄 때 경우의 수를 h(n)이라고 하면, h(n) = g(n) + h(n-5)이다.

 

n=0부터 5까지 h(n)의 값을 구해보면 다음과 같다.

h0)	h(1)	h(2)	h(3)	h(4)	h(5)
1	1	2	2	3	4

 

값이 계산되는 방식을 살펴보면, 한 종류의 동전으로 0부터 n까지의 거스름돈을 주는 경우의 수를 구한 뒤, 동전을 한 종류씩 더해서 다시 경우의 수를 구하고 있다.

 

이를 코드로 작성하면 아래와 같다.

코드

function solution(n, money) {
    let dp = new Array(n + 1).fill(0);
    dp[0] = 1;

    for (var i = 0; i <= money.length; i++) {
        for (var j = money[i]; j <= n; j++) {
            dp[j] += dp[j - money[i]];
            dp[j] %= 1000000007;
        }
    }

    return dp[n];
}

결과

후기

풀고보니 간단한 문제였지만, 재귀함수가 막히고 새로운 접근 방식을 찾는데 시간이 오래 걸렸다.

글로 설명하려는 부분도 잘 전달되었는지 모르겠다.

 

그리고 사실 처음에는 효율성 테스트에서 시간초과가 발생했다.

원인은 BigInt를 사용한 것이었다.

지난 문제에서 큰 정수를 다룰 때 BigInt를 사용해야했었는데, 이번 문제도 입력값이 너무 커지면 dp배열에 담을 숫자가 Number범위를 넘는 문제 때문에 BigInt를 사용해서 문제를 해결했다.

그러나 BigInt는 Number보다 시간 효율이 떨어져 효율성 테스트를 통과할 수 없었다.

 

BigInt로 결과를 계산한 뒤 마지막에 10000007로 나누는 방법이 아니라, 애초에 dp배열에 숫자를 담을 때 10000007로 나눈 나머지를 담는 방법으로 해결했다.

이게 가능한 이유는 이 문제에서 사용하는 연산이 덧셈 연산이었기 때문이다.

만약 숫자를 곱한 뒤에 나머지를 구하라고 했으면 어쩔 수 없이 BigInt를 써야 했을 것이다.