백준 15988번 1,2,3 더하기 3 풀이 - node.js

해당 포스팅은 백준 15988번 1,2,3 더하기 3 풀이를 다룬다. 문제 링크
코드는 javascript로 작성하였다.

문제

• 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하라.
• 예제: 정수 4
  정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.
  • 1+1+1+1
  • 1+1+2
  • 1+2+1
  • 2+1+1
  • 2+2
  • 1+3
  • 3+1

입력

• [첫째 줄] : 테스트 케이스의 개수 T
• [둘 째줄 ~ ] : 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. (1 <= n <= 1,000,000)

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

풀이

이 문제는 백준의 1,2,3 더하기 풀이와 n의 범위만 다르다. 이전 문제와 동일하므로 전반적인 풀이 과정은 생략하겠다.
1,2,3 더하기 풀이는 이전 포스팅을 참고하자. 1,2,3 더하기 풀이

n이 1,000,000 이하 양수이므로 재귀로는 절대 풀 수 없다. 따라서 반복문을 이용해 풀자.

코드 설명

• 테스트케이스 중 가장 n이 큰 케이스에 대해서만 memo를 구하자.
• dp 함수를 구현한다.
  • n이 4 이하일 땐 memo의 값을 리턴한다.
  • n이 5 이상일 때는 while문을 돌려 memo를 채워준다.
  • while문 탈출 시 memo를 리턴한다.
• 테스트 케이스들을 순회하면서 memo[n]을 출력해준다.

전체 코드

const input = require('fs').readFileSync('/dev/stdin').toString().split("\n");
const [T, ...test] = input;

let maxCase = dp(Math.max(...test));

function dp(n, memo=[0,1,2,4]){  
  if(n <= 4){
    return memo[n-1];
  }
  let i = 4;
  while(i <= n){
    memo[i] = (memo[i-1] + memo[i-2] + memo[i-3])%1000000009;
    i++;
  }
  return memo;
}

const answer = [];
test.map(el => {
    answer.push(maxCase[el]);
})

console.log(answer.join("\n"));