백준 15988번: 1, 2, 3 더하기 3 - javascript

백준 15988번: 1, 2, 3 더하기 3

문제 설명

정수 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

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 1,000,000보다 작거나 같다.

출력

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

접근

아주 전형적인 dp문제인데, 기본형태는 [백준 9095번] 문제다.
그때는 n의 값이 11 이하로 제한되어있어서 그냥 top-down방식의 재귀로 풀었었는데, 이번에는 n이 1,000,000 까지 주어진단다. 딱 봐도 top-down으로 풀다간 콜백에러가 날것이 뻔했다.

먼저 풀이 자체는 간단하다.
주어진 조건은 n을 1, 2, 3의 합으로만 나타낸다는 것이다. 따라서 n 은 몰라도 당장 1을 1,2,3으로 나타내는 법, 2를 1,2,3으로 나타내는 법, 3을 1,2,3으로 나타내는 법은 알 수 있다.

n	1	2	3	4
-	1	2	4

이제 위의 표를 참고해서 n이 4인 경우를 찾는다.

4 = 1 + 3
  = 2 + 2
  = 3 + 1

4는 이렇게 1,2,3으로 나타내면 각자 3,2,1이 남는다. 하지만 우리는 이미 위의 표를 통해서 3,2,1일때 방법이 몇 가지인지 알 수 있다.

5의 경우에도

5 = 1 + 4
  = 2 + 3
  = 3 + 2

식으로 나타낼 수 있고, 4,3,2일때 방법가짓수는 이미 앞의 4의 경우를 구하면서 구할 수 있다.

위의 2번의 반복된 경과를 통해서 우리는 dp[n] = dp[n-1] + dp[n-2] + dp[n-3] 이라는 점화식을 도출 할 수 있다.

여기서 이전에는 dp를 function으로 짜서 재귀형식으로 풀었는데, 이번에는 범위가 크므로 3부터 n까지 dp배열을 가지고 가는 반복문을 통해서 완성했다.

그런데 시간초과가 났다.

왜 일까. 생각해보니 내가 작성한건 한번의 독립시행의 n에 대한 결과값을 알려주는 n-3번의 반복문이다. 그런데 테스트 케이스 횟수로 T가 주어지고 1,000,000이하의 N을 주어진다. 즉 최악의 경우 1,000,000의 반복문을 T번 시행해야 할 수도 있는 것이다. 따라서 나는 메인함수에서 입력받은 테스트 케이스들 중 max값을 찾아서 한 번의 시행만 거치고 배열을 반환 받아서 정답을 출력하게 변경해서 시간초과를 통과했다.

정답 코드

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
let input = [];
rl.on('line', function (line) {
  input.push(line)
})
  .on('close', async function () {
  // 답안 작성
  input.splice(0,1);
  let arr=[1,2,4];
  let answer =[];
  let result = dfs_plus_two(Math.max(...input),arr);  
  input.reduce((acc,cur)=>{
    answer.push(result[cur-1]);
  },'');
  console.log(answer.join('\n'));
  
  process.exit();
});

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