[백준 | JavaScript] 9095 1,2,3더하기

<문제 설명>

<문제 풀이>

const fs = require("fs");
let input = fs.readFileSync(0).toString().trim().split('\n').map(Number)
let dp = [0,1,2,4] //0,1,2,3에서의 결과값

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

1,2,3의 합으로 나타낸다는 것은 1,2,3이 계속해서 반복된다는 뜻이다.

그래서 처음으로 반복되는 것이 계속해서 추가된다는 것이 생각이 났다. 

그런데 점화식이 a(n) = a(n-1) + a(n-2)라는 것은 배웠는데,

어떻게 적용해야 할지 막막했다. dp는 동적 계획법으로 알고리즘의 유형 중 하나인데,

이 문제는 전형적인 문제인 것 같다. 따로 이 부분은 공부하며 포스팅해봐야겠다. 

 

이 문제에서는 특정 값을 1,2,3으로 만들 수 있는 경우의 수를 구하는 것이므로 

어떤 조합이 나오는지 구하는 것이 아니라 그 조합의 총 가짓수만 구하면 된다. 

 

0은 1,2,3으로 만들 수 없고, 1은 1의 한 가지 경우가 있다. 

2는 1+1,2가 있고, 3은 1+1+1, 1+2, 2+1, 3이라는 4가지 경우가 있다. 

문제의 예시로 값이 4일 때 나오는 경우가 7이라고 적혀있다. 

dp(0)=0, dp(1) = 1,  dp(2) = 2, dp(3) = 4, dp(4)= 7 이다. 

dp(4) = dp(3)+dp(2)+dp(1)이 된다. 

dp(i) = dp(i-1)+dp(i-2)+dp(i-3)으로 바꿔볼 수 있겠다. 

 

dp(3)을 구하려면 dp(0)이 들어가는데, 그 값은 1,2,3을 쓰지 않으므로 dp(4)부터 가능하다.

그래서 dp1,2,3의 값을 구할 경우를 위해 1,2,3의 결과값을  한 배열에 저장하고,

dp[n]의 값을 구하기 위해 n을 입력하면, n이 0,1,2,3일 경우 배열 안의 값을 반환한다.

그리고 4부터는 아래의 식의 값이 반환된다.

 

<코멘트>

풀면서 이 알고리즘이 떠올랐는데, 어떻게 사용해야 할지 막막해서 찾아가면서 풀었다보니

내가 0부터 생각해가며 푼게 아니여서 설명하기가 어려웠다. 

포스팅하면서 차근차근 되짚는게 도움이 되는 것 같다.