[백준 9095번] 1, 2, 3 더하기 - 자바스크립트(nodejs)

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

9095번: 1, 2, 3 더하기

const fs = require('fs');

let [n, ...input] = fs.readFileSync('dev/stdin').toString().trim().split('\n');
input = input.map(Number);

const occation = [0];

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

for (let i = 4; i <= Math.max(...input); i++) {
  occation[i] = occation[i - 3] + occation[i - 2] + occation[i - 1];
}

input.forEach((v) => {
  console.log(occation[v]);
});

DP같은 문제를 볼 때 재귀로 막 돌릴 생각보다 DP로 메모하면서 풀 문제인지 파악한다. 그리고 점화식을 생각해본다.

위 문제는 

1을 1,2,3을 이용해 만드는 경우의 수 : 1

2를 1,2,3을 이용해 만드는 경우의 수 : 2

3를 1,2,3을 이용해 만드는 경우의 수 : 4

4를 1,2,3을 이용해 만드는 경우의 수 : 7

이 안에서 N을 1,2,3을 이용해 만드는 경우의 수 : N-1, N-2, N-3의 경우의 수를 모두 합하면 된다는 점화식을 유추할 수 있다.

왜 이렇게 나오는 지 생각해보자.

 

1 =>

   1

  => 1가지

2 =>

   1에서 1+1

   2

   => 2가지

3 =>

   1에서 1+2,

   2에서 1+1+1

   2에서 2+1

   3에서 3

  => 4가지

4 =>

   1에서 1+3

   2에서 1+1+2, 2+2

   3에서 1+1+1+1, 1+2+1, 2+1+1, 3+1

   => 7가지

 

규칙을 보면 이전 숫자들을 참고해서 1씩 더해 해당 숫자를 구하는 모습을 볼 수 있다.