금고털이 (DP, Knapsack)

문제

도쿄는 알고리즘을 이용해 target 금액을 훔칠 수 있는 방법의 경우의 수를 계산합니다.

예를 들어 $50 을 훔칠 때 $10, $20, $50 이 있다면 다음과 같이 4 가지 방법으로 $50을 훔칠 수 있습니다.

• $50 한 장을 훔친다
• $20 두 장, $10 한 장을 훔친다
• $20 한 장, $10 세 장을 훔친다
• $10 다섯 장을 훔친다

훔치고 싶은 target 금액과 금고에 있는 돈의 종류 type 을 입력받아, 도쿄가 target 을 훔칠 수 있는 방법의 수를 리턴하세요.

입력

인자 1: target

• Number 타입의 100,000 이하의 자연수

인자 2: type

• Number 타입을 요소로 갖는 100 이하의 자연수를 담은 배열

출력

• Number 타입을 리턴해야 합니다.
• 조지가 target을 훔칠 수 있는 방법의 수를 숫자로 반환합니다.

주의사항

모든 화폐는 무한하게 있다고 가정합니다.

입출력 예시

나의 코드

동적 계획법(Dynamic Programing, DP)를 활용합니다. 주어진 문제를 각각의 경우의 수로 쪼갤 수 있고, 그 경우의 수가 다음 경우의 수를 구할 때 사용되기때문에, 반복적인 연산을 최소화할 수 있습니다.

목표 금액이 50, 돈의 종류가 [10, 20, 50]이라 예시를 들어보겠습니다.

돈의 종류가 3개가 있고, 3 종류의 돈으로 목표 금액을 훔칠 수 있는 경우의 수를 구해야 합니다.

즉, 10원일 때, 20원일 때, 10원 + 20원일 때... 등등 경우의 수를 잘게 쪼개고, 최종적으로 그 경우의 수를 모두 합하는 것으로 동적 계획법을 사용한다는 근거가 만들어졌습니다.

	0원	10원	20원	30원	40원	50원
10원
20원
50원

표의 가로는 0원부터 목표 금액까지 훔칠 수 있는 액수의 모든 경우입니다.

표의 세로는 주어진 돈의 종류(10원, 20원, 50원) 입니다.

먼저 10원만으로 목표 금액인 50원을 훔치는 경우의 수를 생각해보겠습니다.

	0원	10원	20원	30원	40원	50원
10원	1
20원	1
50원	1

주어진 돈으로 0원을 훔치는 경우는 아예 훔치지 않는 경우가 있으므로 1입니다.

10원으로 훔칠 수 있는 경우의 수는 10원을 훔치던, 50원을 훔치던 1입니다. (10원 1개, 10원 5개)

	0원	10원	20원	30원	40원	50원
10원	1	1	1	1	1	1
20원	1
50원	1

20원으로 목표 금액을 훔치는 경우는 목표 금액이 20원일 때, 40원일 때 입니다.

	0원	10원	20원	30원	40원	50원
10원	1	1	1	1	1	1
20원	1	0	1	0	1	0
50원	1

그러나, 10원과 20원으로 목표 금액을 훔치는 경우는 이야기가 다릅니다.

목표 금액이 30원일 때(10원 + 20원), 50원일 때(10원 1개 + 20원 2개, 10원 3개 + 20원 1개)가 있습니다. 그리고, 40원(10원 2개 + 20원 1개)일 때에도 경우의 수가 있습니다.

10원과 20원으로 만들어지는 경우의 수는 아래와 같습니다.

	0원	10원	20원	30원	40원	50원
10원	1	1	1	1	1	1
20원	1	1	2	2	3	3
50원	1

50원도 마찬가지로 아래와 같습니다.

50원으로 훔치는 경우

	0원	10원	20원	30원	40원	50원
10원	1	1	1	1	1	1
20원	1	1	2	2	3	3
50원	1	0	0	0	0	1

10원과 50원으로 훔치는 경우

	0원	10원	20원	30원	40원	50원
10원	1	1	1	1	1	1
20원	1	1	2	2	3	3
50원	1	1	1	1	1	2

10원, 20원, 50원으로 훔치는 경우

	0원	10원	20원	30원	40원	50원
10원	1	1	1	1	1	1
20원	1	1	2	2	3	3
50원	1	1	2	2	3	4

즉, 10원, 20원, 50원으로 50원을 훔칠 수 있는 경우의 수는 4개입니다.

일련의 규칙성이 있습니다.

기존 경우의 수에 현재 돈의 종류를 뺀 경우의 수를 더하는 것 입니다.

아무것도 훔치지 않는 경우를 제외하고,

• 50원으로 훔치는 경우는 [0,0,0,0,1]

• 10원과 50원으로 훔치는 경우는 10원과 50원 중 뒤에 있는 돈의 종류(50원)을 뺀 경우, 즉 10원으로 훔치는 경우 [1,1,1,1,1]

• 두 경우를 더하여 [1,1,1,1,2] 가 나오게 된 것입니다.

• 10원, 20원, 50원으로 훔치는 경우는 마찬가지로 50원으로 훔치는 경우 [0,0,0,0,1] 와

• 10원, 20원으로 훔치는 경우 [1,2,2,3,3] 를 더합니다.

코드는 아래와 같습니다.

결과

소스코드

function moneyHeist(target, type) {
  // 목표 금액 + 1을 길이로 새로운 배열을 만듭니다.
  // 경우의 수를 저장하기 위해 최초로 0을 할당합니다.
  // 배열의 인덱스는 목표 금액이 됩니다.
  // 목표 금액이 0인 경우는 아무것도 훔치지 않는 경우가 있으므로
  // 0번째 인덱스 값을 1로 할당합니다.
  let dp = new Array(target + 1).fill(0);
  dp[0] = 1;
  for (let i = 0; i < type.length; i++) {
    // 돈의 종류로 들어온 배열을 반복 순회합니다.
    // 만약 10원으로 10원을 만드는 경우는 오직 1개이므로
    // 그 값을 인덱스로 가지는 dp 배열에 1을 증가시킵니다.
    dp[type[i]] += 1;
    for (let j = type[i] + 1; j <= target; j++) {
      // 10원과 20원으로 20원을 만드는 경우는
      // 20원만으로 20원을 만드는 경우에
      // 10원만으로 20원을 만드는 경우를 더해야합니다.
      dp[j] += dp[j - type[i]];
    }
  }
  return dp[target];
}