백준 9095번 1,2,3 더하기

내가 푼 코드

와 내가 제대로 안구해서 이상하게 규칙이 안찾아졌던 것.

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n').map(x=>+x);

let n = input.shift();
let answer = '';
///1시간 고민함
for(let i=0; i < n; i++) {
    answer += count(input[i]) + '\n';
}

console.log(answer);
function count(n) {
    let arr  = new Array(n+1).fill(0);
    arr[1] = 1 
    arr[2] = 2
    arr[3] = 4;
    for(let i=4; i <= n; i++) {
        arr[i] = arr[i-1] + arr[i-2] + arr[i-3];
    }
    return arr[n];
}

1: 1
2: 2
3: 4
4: 7
5: 13
6: 24
7: 44

F(n) = F(n-1) + F(n-2) + F(n-3) 이라는 규칙이 찾아진다.
이 규칙을 토대로 피보나치 수열을 구하는 것처럼 풀면된다.

---

저걸 단순히 규칙을 찾아서 하는 게 아니라
1을 더하는 경우는 dp[n-1]에 구한 수들에 1을 더하는 거고
2를 더하는 경우는 dp[n-2]에 구한 수들에 2을 더하는 거고
3을 더하는 경우는 dp[n-3]에 구한 수들에 3을 더하는 거다.

그래서 dp[n] = dp[n-1] + dp[n-2] + dp[n-3] 이런 점화식이 도출되는 것.

설명 참고 블로그