해당 포스팅은 백준 9095번 1, 2, 3 더하기 풀이를 다룬다. 문제 링크
코드는 javascript로 작성하였다.
T
n
이 주어진다.(1 <= n <= 11
)각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.
n이 5일 때를 구해본다고 가정해보자.
위의 사진을 보면 n=4
부터 dp(n-1)
, dp(n-2)
, dp(n-3)
의 값을 이용한 것을 확인할 수 있다.
그 이유는 이전의 값 dp(n-1), dp(n-2), dp(n-3)
에 1,2,3을 각각 더했을 때 n이 나오기 때문이다.
점화식
dp(n) = dp(n-1) + dp(n-2) + dp(n-3)
메모이제이션
하였으며, n이 11 이하이므로 재귀
로 풀어보았다.max 케이스의 부분합
이므로, n이 max일 때의 memo를 구한 후 케이스들의 결과를 memo의 인덱스로 접근한다.[0, 1, 2, 4]
로 정의해준다.const input = require('fs').readFileSync('/dev/stdin').toString().split("\n");
const [T, ...test] = input;
const memo = [0, 1, 2, 4];
function dp(n) {
if (memo[n] !== undefined) return memo[n];
memo[n] = dp(n-1) + dp(n-2) + dp(n-3);
return memo[n];
}
dp(10);
const answer = test.map(el => {
return memo[el];
})
console.log(answer.join("\n"))
처음에는 모든 케이스에 대해 재귀를 돌렸더니 틀렸다고 했다!
그래서 테스트케이스 중 가장 큰 n에 대해서만 재귀를 돌린 다음, 각 케이스의 결과를 memo의 인덱스로 출력해주었더니 통과했다.
연산을 최적화해주지 않았다고 시간 초과가 아닌 "틀렸습니다"가 뜨는게 신기했다.
const input = require('fs').readFileSync('/dev/stdin').toString().split("\n");
const [T, ...test] = input;
function dp(n, memo=[0,1,2,4]) {
if (memo[n] !== undefined) return memo[n];
memo[n] = dp(n-1) + dp(n-2) + dp(n-3);
return memo[n];
}
const answer = test.map(el => {
return dp(Number(el))
})
console.log(answer.join("\n"));