[프로그래머스] LV.3 거스름돈 (JS)

문제

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

입출력 예시

n	money	result
5	[1,2,5]	4

풀이

다른 DP 문제에 비해서 생각보다 난이도가 있는 문제이다. 시간복잡도뿐만 아니라 DP 배열의 공간복잡도도 생각해서 풀이해야 통과하는 경우가 많다. 물론 공간복잡도를 잘 설계하면 다른 방식으로도 통과할 수 있다. 일단 왜 DP로 해당문제를 접근해야 하는지부터 살펴보자.

문제에서 주어진 예시는 n이 5이고 화폐는 [1, 2, 5]로 3종류가 주어졌다. 즉 3가지 화폐를 가지고 5원의 거스름돈을 만들 수 있는지 검사해야 한다. 이는 문제 설명에서도 나왔듯이 다음과 같이 간단하게 나타낼 수 있다.

• 1원을 5개 사용해서 거슬러 준다.
• 1원을 3개 사용하고, 2원을 1개 사용해서 거슬러 준다.
• 1원을 1개 사용하고, 2원을 2개 사용해서 거슬러 준다.
• 5원을 1개 사용해서 거슬러 준다.

이것만 언뜻 봐서는 중복되는 연산이 잘 보이지가 않는다. 그렇다고 위의 방식 그대로 모든 조합(Combination)을 구해 일일이 경우의 수를 계산하려 한다면 시간복잡도가 초과될 것이다. 다른 방식으로 잠깐 바꾸어 생각해보자.

1. 1원을 사용해서 5원의 거스름돈을 만드는 법은 1원을 5개 사용하는 것이다. 그렇다면 1원을 사용해서 만들 수 있는 모든 거스름돈은 1원부터 5원까지가 될 것 이다.

2. 2원을 사용해서 5원의 거스름돈을 만드는 법은 2원만 사용해서는 불가능하다. 5는 2로 나누어 떨어지지 않기 때문이다. 하지만 2원을 몇 개만 사용해서 5원을 만드는 것은 가능하다. 위의 경우의 수 처럼 2원을 1개만 사용하는 경우와 2개를 사용하는 경우가 있다. 나머지 채워지지 않는 거스름돈은 1원으로 다 채울 수 있다. 또한 2원을 사용해서 만들 수 있는 거스름돈은 최소 2원 이상 부터 가능하다.

3. 5원을 사용해서 5원의 거스름돈을 만드는 법은 오직 1가지 경우만이 가능하다. 5원 하나만 사용하는 경우이다. 5원을 사용해서 거스름돈을 만들 수 있는 최소값은 5원인데, 여기선 n이 5이기 때문에 그 이하의 값은 5원을 사용해서는 절대 만들 수가 없다.

위의 흐름으로 보았을 때 우리는 2번의 과정에서 이전에 이용한 1원의 결과 몇 개를 들고오는 것을 볼 수 있다. 3번 역시 마찬가지인데, 마지막 5원을 만드는 경우의 수는 이전 1원과 2원을 이용해서 5원을 만든 경우의 수 + 자기자신으로 계산할 수 있을 것이다. 그렇다면 우리는 DP 배열을 다음과 같이 정의할 수 있다.

• DP[i][j] = 화폐를 i+1개 사용해서 거스름돈 j를 만들 수 있는 경우의 수

이때 i+1 자체에 크게 신경 쓸 필요는 없다. index는 0부터 시작하지만 우리는 화폐를 1개부터 사용해서 거스름돈을 만들어줄 거기 때문에 거기서 오는 차이라고만 보면 된다. 또한 거스름돈 j는 위에서 보았듯이 1원부터 n원까지 모든 금액에 대한 케이스를 제시해야 한다. 그래야 위 과정에서 이전 결과로 구해놓은 경우의 수를 정상적으로 가져올 수 있다. 위의 입력을 가지고 예를 들면 다음과 같다.

• DP[0][5] : 화폐 1개(1원)를 사용하여 거스름돈 5원을 만들 수 있는 경우의 수
• DP[1][3] : 화폐 2개(1원과 2원)를 사용하여 거스름돈 3원을 만들 수 있는 경우의 수
• DP[2][4] : 화폐 3개(1원, 2원 그리고 5원)를 사용하여 거스름돈 4원을 만들 수 있는 경우의 수
• ...

따라서 i는 money.length의 크기만큼, j는 0부터 n의 범위만큼의 크기를 가진 2차원 배열을 선언해줄 수 있다. 즉 다음과 같이 배열을 선언해보자.

const dp = new Array(money.length).fill().map(_ => new Array(n+1).fill(0);

위와 같이 2차원 배열을 선언하면 우리는 화폐를 1개부터 사용하여 n개까지 사용하면서 1원부터 n원까지 모든 금액에 대한 경우의 수를 지정할 수 있을 것이다. 이때 n+1 에 주목하자. 이는 1원 부터가 아니라 0원 부터 체크를 하겠다는 의미인데, 왜 0원에 대한 경우도 같이 생각하는 것일까? 이는 계산의 편의를 위해 0원 부터 고려해주는 것이다. 자세한 내용은 아래에서 계속 살펴보자.

위와 같이 DP배열을 만들면 다음과 같은 테이블을 그릴 수 있다. 이때 0원을 거슬러줄 수 있는 경우의 수는 모두 1로 통일하자. 논리적으로 0원을 어떻게 화폐를 사용해서 거슬러줄 수 있는가에 의문이 갈 수 있는데, 사실 계산 편의를 위해 넣어주는 것으로 생각하고 넘어가도 좋다. 거스름돈 0원이 1회로 측정되는 이유는 화폐를 아무것도 사용하지 않는 것 역시 1가지 경우의 수로 취급하기 때문이다.

DP	0	1	2	3	4	5
0 (1원)	1	0	0	0	0	0
1 (1원, 2원)	1	0	0	0	0	0
2 (1원, 2원, 5원)	1	0	0	0	0	0

다음과 같이 DP 배열이 초기화가 되었을 것이다. 그럼 이제 첫번째 행에 1원 하나만 사용해서 1 - 5까지 거스름돈을 만들 수 있는 경우의 수를 넣어주자. 1원은 각각의 경우를 모두 만들 수 있기 때문에 첫번째 행은 모두 1이 될 것 이다.

DP	0	1	2	3	4	5
0 (1원)	1	1	1	1	1	1
1 (1원, 2원)	1	0	0	0	0	0
2 (1원, 2원, 5원)	1	0	0	0	0	0

두번째 행은 1원과 2원을 사용해서 해당하는 거스름돈을 만들 수 있는지에 대한 경우의 수를 저장한다. 여기서 우리는 거스름돈이 2원이 되기 전까지는 이전의 경우의 수와 완벽하게 동일하다는 것을 알 수 있다. 왜냐하면 새로운 화폐가 등장하기 전까지는 지금 거스름돈에 대해 새롭게 화폐를 사용해서 만들 수 있는 경우의 수가 존재하지 않기 때문이다. 즉 거스름돈이 2원 이상일때부터 새로운 화폐인 2원을 사용하여 만들어줄 수 있는 가능성이 생긴다. 그렇다면 DP[1][2]을 어떻게 계산하는지 살펴보자. 먼저 기존의 경우는 무조건 가능하다. 여기서 기존의 경우란 1원 하나만 사용해서 거스름돈 2원을 만드는 경우, 즉 DP[0][2]를 말한다. 현재 DP가 1원과 2원을 모두 사용하여 만드는 경우이기 때문에, 기존의 경우를 포함하고 있기 때문이다. 그리고 현재 거스름돈이 2원이기 때문에 자기자신을 기존의 경우에 더해줄 수 있다. 따라서 DP[1][2] 의 값은 2가 될 것이다. 그렇다면 거스름돈이 3원 이상이 되는 경우는 어떻게 구해줄까? 이 경우에도 기존의 경우는 포함하고 있기 때문에 DP[0][3]의 경우의 수는 무조건 가능하다. 그리고 DP[1][현재 거스름돈 - 새로 추가된 화폐 금액]에 있는 값을 기존의 경우에 더해주면 DP[1][3]을 구할 수 있다. 즉 위의 사례에서는 DP[0][3] + DP[1][1]의 값이 DP[1][3]이 되는 것이다. 왜 이것이 성립할까?

그 까닭은 2원을 넘는 금액은 모두 2원을 최소 1번은 사용이 가능하다. 따라서 현재 거스름돈으 만들기 위해 2원을 한 번 사용했다고 가정하고 현재 거스름돈에 2원을 제외한 그 차액을 다시 현재 가지고 있는 화폐인 1원과 2원으로 만들 수 있는지를 검사하는 것이다. 여기서 2원을 한 번 사용했다고 가정한다고 무조건 1을 더해주는 것이 아니다. 왜냐하면 1번 사용했다고 하더라도 해당 거스름돈을 만들지 못하는 경우의 수가 존재할 수 있기 때문이다. 거스름돈이 현재 화폐와 동일한 경우에는 무조건 가능해서 1을 더해주었지만, 이를 초과하는 금액은 항상 그렇지 않다. 따라서 다음의 점화식을 찾아낼 수 있다.

1. 현재 거스름돈이 새로 추가된 화폐 단위와 동일한 경우 : DP[i][j] = DP[i-1][j] + 1
2. 현재 거스름돈이 새로 추가된 화폐 단위를 초과한 경우 : DP[i][j] = DP[i-1][j] + DP[i][j - 추가된 화폐 금액]

그런데 앞서서 우리는 계산의 편의를 위해 거스름돈 0원을 만들어 이를 모두 1로 초기화 해주었다. 이는 바로 지금 이 순간을 위한 것이다. 거스름돈 0원을 모두 1로 초기화해주었다면, 우리는 위 점화식처럼 두 조건으로 분기할 필요없이 2번 조건으로 모두 적용이 가능하다. 왜냐하면 현재 거스름돈과 추가된 화폐 금액이 동일하면 무조건 1회 사용이 가능한 것을 앞서 살펴보았고, 현재 거스름돈 - 추가된 화폐 금액 는 항상 0이기 때문이다. 따라서 0의 인덱스를 모두 1회 사용이 가능하다는 뜻에서 1로 초기화를 한 것이다.

세번째 행은 1원과 2원, 그리고 5원을 이용해 해당 거스름돈을 만들 수 있는지에 대한 경우의 수를 저장한다. 앞에서 설명한 바와 같이 0원부터 4원까지는 5원을 새로 사용할 수 없기 때문에 이전의 행과 동일하다. 거스름돈이 5원이 되면 추가된 화폐 5원을 사용할 수 있고, 위의 점화식에 따라서 DP[2][5] = DP[1][5] + DP[2][0]이 될 것이다. 여기까지 반복문을 모두 돌았다면 테이블은 다음과 같이 구성될 것 이다.

DP	0	1	2	3	4	5
0 (1원)	1	1	1	1	1	1
1 (1원, 2원)	1	1	2	2	3	3
2 (1원, 2원, 5원)	1	1	2	2	3	4

우리가 구하고자 하는 값은 DP[2][5]에 들어있으니 해당 값을 리턴해주면 될 것 이다.

그런데 여기서 한 가지를 더 딥하게 생각해 볼 수 있다. 굳이 2차원 배열을 써서 풀이해야 할까? (물론 2차원 배열로 짜도 통과가 가능하다)
앞에서 점화식을 찾아내면서 우리는 중요한 포인트를 하나 발견했는데, 이는 현재 거스름돈이 추가된 화폐금액과 동일해지기 전까지는 이전의 행과 그 내용이 동일하다는 점이다. 이를 이용해서 우리는 배열을 1차원 배열로 바꾸어 공간복잡도 역시 효율적으로 개선할 수 있다. (이 부분이 잘 이해가 되지 않는다면 다음도 같이 생각해보자. backtracking의 대표문제인 N-Queen에서 1차원 배열을 사용하여 해결하는 것과 유사한 관점이다) 즉 기존의 DP[i][j] 에서 우리는 i 부분을 버릴 수 있다. 화폐를 몇 개 썼는지에 대한 여부는 굳이 저장해주지 않아도 새롭게 화폐가 추가되는 시점에만 값의 변동이 생기기 때문에 우리는 현재 거스름돈 j가 새로 추가되는 화폐 money[i] 보다 크거나 같은지만 조건으로 걸러주면 된다. 따라서 DP[j]는 이미 DP[i-1][j] 값을 가지고 있는 상태가 되므로 여기에 DP[j - money[i]] 만 더해주면 된다. 이를 다시 적용해서 DP배열의 초기화부터 점화식을 구현한 부분을 코드로 살펴보자.

// dp 배열은 더이상 2차원 배열일 필요가 없다.
// n+1 크기의 1차원 배열로 만들어준다.
// n+1 크기인 이유는 위에서 설명한 바와 같이 0을 계산의 편의를 위해 사용해주기 위해서다.
// 때문에 첫번째 원소값은 1, 그리고 나머지는 주어진 n의 크기만큼 선언한다.
const dp = [1, ... new Array(n).fill(0)];

// 가지고 있는 화폐 개수만큼 반복문을 돌 것이다.
// 따라서 money[i]는 항상 새롭게 추가되는 화폐 금액 단위가 들어있다.
for(let i = 0; i < money.length; i++) {
  // j는 0부터 n까지에 이르는 모든 현재 거스름돈이다.
  for(let j = 0; j <= n; j++) {
    // 현재 거스름돈이 새롭게 추가된 화폐 단위와 같거나 크다면
    // 새롭게 추가되는 화폐를 사용할 수 있다는 뜻이므로
    // 위에서 찾은 점화식을 적용하여 dp 배열을 구한다.
    if(j >= money[i]) {
      // dp[j]는 위 조건에 의해 새로운 화폐가 추가될 때 진입되므로
      // 기존에 구한 dp[j]는 모두 2차원 배열에서의 이전 행에서의 값과 동일하다. 
      dp[j] += dp[j - money[i]];
    }
  }
}

코드 자체는 길이도 짧고 비교적 단순하나 이처럼 생각하기가 여간 까다로운 문제였던듯 하다. 지금까지 포스팅한 Lv.3 DP 문제중에서도 유독 난이도가 높은 것 같다. (물론 Lv.4로 가면 더 어려운게 천지 삐까리다) 구현 자체는 쉽지만 모든 DP 문제가 그렇듯 어떤 식으로 접근할 지에 대한 고민이 깊은 문제였다. 아래는 주석을 제외한 전체 코드이다.

문제에서는 1,000,000,007로 나눈 나머지를 요구하고 있지만 이를 적용하지 않아도 정상 통과하는 점을 확인했다.

코드

function solution (n, money) {
  const dp = [1, ...new Array(n).fill(0)];
  
  for(let i = 0; i < money.length; i++) {
    for(let j = 0; j <= n; j++) {
      if(j >= money[i])
        dp[j] += dp[j - money[i]] & 1000000007;
    }
  }
  
  return dp[n];
}

출처

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