[JavaScript] DP : 짐 나르기

문제

자신이 감옥에 간 사이 연인이었던 줄리아를 앤디에게 빼앗겨 화가 난 조지는 브레드, 맷과 함께 앤디 소유의 카지노 지하에 있는 금고를 털기로 합니다. 온갖 트랩을 뚫고 드디어 금고에 진입한 조지와 일행들. 조지는 이와중에 감옥에서 틈틈이 공부한 알고리즘을 이용해 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을 훔칠 수 있는 방법의 수를 숫자로 반환합니다.

주의사항

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

입출력 예시

let output = ocean(50, [10, 20, 50]);
console.log(output); // 4

let output = ocean(100, [10, 20, 50]);
console.log(output); // 10

let output = ocean(30, [5, 6, 7]);
console.log(output); // 4

Hint!

해당 문제는 동전 교환 알고리즘 (Coin Change)을 활용하여 풀 수 있습니다.
검색해 보시고, 연구해 보세요!

풀이

힌트에 나온 동전 교환 알고리즘 (Coin Change)은 이미 내가 최근에 풀어봤던 문제의 해결과정 및 답을 말한다.
풀었던 글 링크
여기서 간단히 말하자면, 원하는 금액에 맞게 일정 종류의 동전들을 이용해서 주되, 그 동전의 개수를 최소화하는 방법을 뜻한다.

로직

이와 비슷한 문제로 2x1 블럭을 놓는 방법에 대한 알고리즘 문제도 있는데, 이건 다음에 포스팅하겠다.
블럭 문제의 경우 1단계 2단계 3단계 등등 여러 개의 블럭을 놓는 방법이 결국 1-2-3단계를 활용한 것들이라는 방법을 응용해서 풀게 된다.
이 문제 또한 1원, 2원, 3원 … 점점 돈의 액수는 커지지만 처음 1-2-3원으로 만들던 방법을 응용한다는 점에서 경우의 수를 더하면 될 뿐이다.

ex) 돈 종류가 [1원, 2원, 5원]이 있을 경우

• 1원 만드는 방법 : 1원 1개 » 1개
• 2원 만드는 방법 : 1원 2개(1원 만드는 법 응용), 2원 1개 » 2개
• 3원 만드는 방법 : 1원 3개(1원 만드는 법 응용), 1원 1개 & 2원 1개(1&2원 만드는 법 응용) » 2개
• 4원 만드는 방법 : 1원 4개, 1원 2개 & 2원 1개, 2원 2개 (3원&1원 + 2원 만드는 법 응용들) » 4개
• 5원 만드는 방법 : 1원 5개, 1원 3개 & 2원 1개, 1원 1개 & 2원 2개, 5원 1개 » 4개
• 6원 만드는 방법 : 1원 6개, 1원 4개 & 2원 1개, 1원 2개 & 2원 2개, 2원 3개, 1원 1개 & 5원 1개 » 5개

위 예시에서 발견한 게 있는가?
바로 ‘특정 종류 돈이 원하는 금액보다 작을 경우 이용된다’라는 것과 ‘이전에 쓰인 방법이 응용된다’이다.
즉 가장 작은 금액의 돈을 먼저 확인, 작거나 같다면 그 금액만큼 들어가는 경우의 수를 더하기, 가 된다.
그래서 알고리즘 순서는 다음과 같다.

1. bag[i]는 i원을 만드는 방법의 종류를 담는다. 우선 bag[0] = 1이 되게끔 bag=[1]을 선언/할당한다. (0원을 만드는 방법은 아무것도 안 내는 방법 1가지뿐이다.)
2. target만큼 bag의 index마다 0을 채워넣는다.(for문 이용 - i)
3. 돈 종류인 type 배열을 for문으로 순회한다. 보통 작은 값부터 적혀 있으므로, 작은 돈 먼저 들어감을 인지한다.
4. 이중 for문(j)으로 target index 1부터(0은 1로 고정) 순회한다. 이러면 type에 있는 돈 종류별로 활용할 수 있는 경우의 수를 더할 수 있게 된다. 단, type[i] <= j 일 경우.
5. bag[n]마다 경우의 수가 쌓여져 있으므로 최종적으로 bag[target]을 return하면 된다.

해답 코드

function ocean(target, type) {
  // 거스름돈 1원, 2원, 3원 등등에 대한 경우의 수를 구한 뒤
  // 큰 거스름돈에 대해 구한다.
  
  // bag[i]에서 i는 맞춰야 하는 금액이다.
  // bag[0]은 0원을 맞춰야 하는데, 아무것도 안 내면 되는 방법 1가지 이므로 1로 지정한다.
  let bag = [1];

  for(let i = 1; i <= target; i++)
  // 아직 경우의 수를 구하지 않았으므로 target까지 0가지로 정해 둔다.
    bag[i] = 0;

  for(let i = 0; i < type.length; i++) {
    for(let j = 1; j <= target; j++)
      if(type[i] <= j)
        bag[j] += bag[j-type[i]];
  }
  return bag[target];
}

기타 - 한마디

개인적으로 Greedy 알고리즘의 심화문제라고 생각한다. 실제로 코드스테이츠 코플릿 리스트에서도 Advanced라고 적혀 있었으니 맞는 듯하다.

카카오페이로 커피사기 ❤️ 토스 계좌로 커피사기 ❤️