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

 

 

나의 풀이

 답이 너무 간단해서 황당했지만, 상당히 애먹었던 문제다. 동적 계획법을 쓴다는 생각 자체를 하질 못했다.

다른 분의 코드를 읽었는데도 불구하고 왜 동적계획법을 쓰는지 이해하기가 힘들었던 문제이기도하다. 그래서 최대한 쉽고 디테일하게 원리를 정리해보고 풀이를 공개해볼까한다.

 

 

따라서 본문에 쓰인 입출력 예제가 아니라 내가 임의로 정한 입출력 예제롤 써볼까한다.

[그림 1] 입출력 예제

 위의 입출력 예제가 뜻하는 것은 다음과 같다. [2, 3, 4, 6] 각 숫자를 무한 번 사용해서 덧셈을 이용하여 6이라는 경우의 수를 만들자.

 

 

위 문제를 풀기위해서는 동적계획법이 필요하다. 그렇다면 동적계획법을 어떻게 써야하는걸까? 

[그림 2] 숫자와 임의배열

 [그림 2]를 보자. 위 테이블은 숫자, 임의배열 두 개의 범주로 나뉘어져있다. 숫자 2는 입력배열 MONEY의 첫 번째 요소다 그리고 임의 배열 첫 인덱스에 1을 준 이유는 2를 이용해서 2를 만든 경우의 수를 뜻하기 때문이다. 따라서 당연히 1일 수 밖에 없다. 그리고 임의 배열에 인덱스 2부터 6까지의 범위를 파란색으로 색칠한 이유는 2를 최소한 한 개 이상써서 덧셈을 이용하여 인덱스 값을 구할 수 있는 경우의 수를 나타내기 위함이다. 만약에 숫자가 3일면, 3부터 6까지의 범위를 탐색하면 된다.

[그림 3] 첫 번째 계산

 경우의 수 코드는 다음과 같다.

for(let i=2; i<n+1; i++){
	dp[i] += dp[i-2];
}

숫자 2를 이용해서 2를 표현할 때는 2를 한 번만 사용하면 된다. dp[2] = dp[2] + dp[0]

숫자 4를 표현하기 위해서는 2를 두 번만 사용하면 된다. dp[4] = dp[4] + dp[2]

숫자 6을 표현하기 위해서는 2를 세 번만 사용하면 된다. dp[6] = dp[6] + dp[4]

 

즉, 변화하기 전 경우의 수에 인덱스 2만큼 작은 경우의 수 값을 더하면 된다. 좀 더 자세하기 풀면 다음과 같다.

2로 2를 표현하기 위해서는 dp[0](자기자신 값, 무조건 1)을 원래 값(0)에 더해주면 2가 된다.

2로 4를 표현하기 위해서는 dp[2](2로 2를 표현하는 경우의 수)에 2를 한 번 더해주면 4가 된다.

2로 6을표현하기 위해서는 dp[4](2로 4를 표현하는 경우의 수)에 2를 한 번 더해주면 6이 된다.

 

 

이것이 1회 반복이다. 다음 반복에서의 변수 값은

[그림 4] 두 번째 계산

 [그림 4]와 같다. 여기서 숫자는 MONEY 배열의 두 번째 원소를 말한다. 현재 임의 배열은 전에 계산했던 값이다. 이번에 우리가 해야할 작업은 2와 3, 덧셈을 이용해서 3부터 6까지 각 수를 표현할 수 있는 경우의 수를 만들어줘야한다.

[그림 5] 두 번째 계산

 

 탐색 범위는 3부터 6까지다. 계산 과정은 다음과 같다.

2와 3을 이용해서 3을 표현하는 방법은 1가지다. dp[3] = dp[3] + dp[0]

2와 3을 이용해서 4를 표현하는 방법은 1가지다. dp[4] = dp[4] + dp[1]

2와 3을 이용해서 5를 표현하는 방법은 1가지다. dp[5] = dp[5] + dp[2](기존에 2로 2를 표현하는 경우의 수 [2]에 3을 추가하면 됨[2,3])

2와 3을 이용해서 6을 표현하는 방법은 2가지다. dp[6] = dp[6](기존에 2로 6을 나타내기 위한 값 [2,2,2]) + dp[3]([3]에 [3]을 추가해서 [3,3])

 

 

여태까지의 과정을 money배열을 모두 탐색할 때까지 반복하면 된다. 프로그램 코드는 다음과 같다.

const solution = (n, money) => {
  let answer = 0;
  let dp = Array(n + 1).fill(0);
  dp[0] = 1;
  money.forEach((el, idx) => {
    for (let i = el; i < n + 1; i++) {
      dp[i] += dp[i - el];
    }
  });
  answer = dp[n] % 1000000007;
  return answer;
}