9095 1, 2, 3 더하기

220503

알고리즘: DP

정수 n 이 1 일 때 조합 (1개)

1

정수 n 이 2일 때 조합 (2개)

1 + 1 2

정수 n이 3일 때 조합 (4개)

1 + 1 + 1
1 + 2
2 + 1
3

그렇다면 정수 n 이 4일 때는? (7개)

정수 3일 때 : 1 + 1 + 1 + 1
정수 3일 때 : 1 + 1 + 2
정수 3일 때 : 1 + 2 + 1
정수 2일 때 : 2 + 1 + 1
정수 2일 때 : 2 + 2
정수 3일 때 : 3 + 1
정수 1일 때 : 1 + 3

이를 DP 식으로 풀어내면,

• 3일 때 조합이 4개 → DP[N-1]
• 2일 때 조합이 2개 → DP[N-2]
• 1일때 조합이 1개 → DP[N-3]

DP[N] = DP[N-1] + DP[N-2] + DP[N-3] 으로 나타낼 수 있다.

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

const dp = new Array(12).fill(0);
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;

input.map((v) => {
  for (let i = 4; i <= v; i++) {
    dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
  }
  console.log(dp[v]);
});

221022

// 메모리: 9328kb
// 시간: 112ms
const [T, ...input] = require('fs')
  .readFileSync('./input.txt')
  .toString()
  .trim()
  .split('\n');
const memo = { 1: 1, 2: 2, 3: 4 };

let result = '';
input.map((n) => {
  const num = parseInt(n);
  for (let i = 4; i <= num; i++) {
    memo[i] = memo[i - 1] + memo[i - 2] + memo[i - 3];
  }
  result += memo[num] + '\n';
});

console.log(result);