[백준]9095번 - 1,2,3 더하기

2022년 02월 28일

[해결 코드]

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");


const [numOfTestCase, ...arr] = input.map((v) => +v);
const DP = new Array(11).fill(0);

DP[1] = 1;
DP[2] = 2;
DP[3] = 4;

for (let i = 4; i < 11; i++) {
  for (let j = 1; j <= 3; j++) {
    DP[i] += DP[i - j];
  }
}
for (let i = 0; i < numOfTestCase; i++) {
  console.log(DP[arr[i]]);
}

[풀이]

처음에 어떻게 접근해야할지 고민하다가 문제에 주어진 예시를 직접 적어 보았더니 규칙을 쉽게 찾을 수 있었다. 다음과 같은 점화식을 구할 수 있다.

DP[N] = DP[N-1] + DP[N-2] + DP[N-3]

DP를 1,2,3의 합으로 나타내는 경우의 수를 담는 배열이라고 정의하고 위의 그림을 코드로 구현했더니 쉽게 해결할 수 있었다.