백준15989 - 1,2,3 더하기 4 (DP) node.js

https://www.acmicpc.net/problem/15989

 

해당 문제는 다이나믹 프로그래밍을 활요해야 풀이해야 시간제한 내에 풀 수 있는 문제다.

비슷한 문제를 풀이하고 풀이 과정을 포스팅한 링크를 남긴다.

2023.11.09 - [개발/algorithm] - 프로그래머스 Lv.3 - 거스름돈 (DP) Python

 

해당 문제의 접근 방법을 소개하기 앞서, 0부터 6까지 [1,2,3]을 활용해서 만들 수 있는 경우를 표로 나타내면 다음과 같다.

	0	1	2	3	4	5	6
1을 사용		1	1+1	1+1+1	1+1+1+1	1+1+1+1+1	1+1+1+1+1+1
1,2를 사용			2	2+1	2+1+1 2+2	2+1+1, 2+2+1	2+1+1+1+1 2+2+1+1 2+2+2
1,2,3을 사용				3	3+1	3+1+1 3+2	3+1+1+1 3+2+1 3+3
경우의 수	1	1	2	3	4	5	7

 

해당 표에서 [1,2,3]을 활용해 4로 만들 수 있는 경우는 총 4가지인데, 이때 재밌는 점은

'1을 사용해서 4를 만드는 경우'인 1+1+1+1은,  '1을 사용해서 3을 만드는 경우'인 1+1+1에서, 단순히 +1 을 추가했다는 점이고,

 

'1,2를 사용해서 4를 만드는 경우' 중 하나인 '2+1+1'은,  '1,2를 사용해서 3을 만드는 경우'인 2+1 에 +1을 추가.

'1,2를 사용해서 4를 만드는 경우' 중 다른 하나인 '2+2'은, '1,2를 사용해서 2을 만드는 경우'인 2 에 +2을 추가했다는 점,

 

마찬가지로, '1,2,3을 사용해서 4를 만드는 경우'인 '3+1'은, 1,2,3을 사용해서 3을 만드는 경우'인 '3'에서 +1 을 추가했다는 것이다.

 

즉, [1,2,3]을 활용해서 4를 만드는 경우는, 4-1 을 만드는 경우, 4-2를 만드는 경우, 4-3을 만드는 경우를 참조해야 한다는 것이며

이는 n이 m을 포함한 경우의 수를 구하기 위해서는 n-m을 만드는 경우에서 참조해야 한다는 것과 같은 말이다.

 

그리고 이를 코드로 옮겨쓰면 다음과 같이 만들 수 있다.

function makingDP(_length) {
  const dp = Array.from({ length: _length + 1 }, () => 0);
  dp[0] = 1;

  [1, 2, 3].forEach((el) => {
    for (let i = el; i < dp.length; i++) {
      dp[i] += dp[i - el];
    }
  });
  return dp;
}

해당 코드는, _length 의 [1,2,3]을 활용하여 _length 를 만드는 경우의 수를 구하는 과정을 담은 코드다.

위 점화식을 응용하여 만들 수 있다.

 

전체 소스 코드

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt")
  .toString()
  .trim()
  .split("\n");

function solution(data) {
  data.shift();

  const testCase = data.map(Number);
  const _max = Math.max(...testCase);

  const dp = makingDP(_max);
  const result = testCase.map((el) => dp[el]);
  console.log(result.join("\n"));
}

function makingDP(_max) {
  const dp = Array.from({ length: _max + 1 }, () => 0);
  dp[0] = 1;

  [1, 2, 3].forEach((el) => {
    for (let i = el; i < dp.length; i++) {
      dp[i] += dp[i - el];
    }
  });
  return dp;
}

solution(input);