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

백준 9095번: 1,2,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은 양수이며 11보다 작다.

출력

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

접근

주어진 정수를 1,2,3 이 3가지 숫자들로 표현하는 경우의 수를 구하는 문제다.
백준 15988문제를 먼저 포스팅하긴 했는데, 포스팅을 보니깐 그때는 내가 top-down의 재귀로 풀었었나보다.
그러니 이번엔 bottom-up으로 풀어보려고 한다.사실 이미 구한 방법이지만
1,2,3의 경우에는 직접 경우의 수를 구해야한다.
1은 1,
2는 1+1, 2,
3은 1+1+1, 1+2, 2+1, 3
이다.
사실 3의 경우부터 슬슬 보이기 시작한다.
3의 경우를 다시 보면,
1 + dp(2), 2+ dp(1), 3 이런식으로 나눠져있다.
1 + 의 경우는 뒤에 2가 남으니깐 위에서 구한 2의 경우 1+1과 2가 나오게 되고,
2 + 의 경우는 뒤에 1만 남으니깐 당연히 올 수 있는 경우는 1 하나뿐이다.
그외에 3은 0 이 남으니깐 3 하나뿐이고.
이런식으로 우리는 다음과 같은 점화식과 초기 배열을 얻을 수 있다.

dp = [0,1,2,4];
dp[i] = dp[i-1] + dp[i-2] + dp[i-3];

왜 dp배열의 맨앞에 0을 넣었냐면 반복문을 사용할때 일일히 dp의 인덱스에 -1 연산을 안해주기 위해 그냥 0인덱스의 값을 새로 만들어놨다.
어차피 i의 최소 시작은 4이므로 영향이 가지는 않는다.

이제 기본 점화식을 만들었고, 우리는 문제에서 첫째 줄에 테스트 케이스 개수 T가 주어진다고 했다.
그 말은 여러개의 숫자가 들어온다는 것이고, 이에 대해서 매번 점화식을 돌려야 할 필요가 없다.
들어온 숫자들 중에서 max값을 먼저 찾아 max값까지 점화식을 돌려주고, 저장한 dp배열에 인덱스값들만 찾아서 테스트 케이스의 결과들을 한 줄씩 출력해주면 된다.

정답 코드

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 () {
  // 답안 작성
  let answer =0;
  answer = plus_number(input);
  console.log(answer);
  process.exit();
});

let plus_number = function(input){
  input.splice(0,1);
  let max = Math.max(...input);
  let result = [0,1,2,4];
  for(i=4;i<=max;i++){
    result[i] = result[i-1] + result[i-2] + result[i-3];
  }
  let answer = [];
  input.reduce((acc,cur)=>{
    answer.push(result[cur]);
  },'')
  return answer.join('\n');
}