백준 9095번 1,2,3 더하기 - node.js

해당 포스팅은 백준 9095번 1, 2, 3 더하기 풀이를 다룬다. 문제 링크
코드는 javascript로 작성하였다.

문제

• 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하라.
• 예제: 정수 4
  정수 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

입력

• [첫째 줄] : 테스트 케이스의 개수 T
• [둘 째줄 ~ ] : 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다.(1 <= n <= 11)

출력

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

풀이

1. 점화식

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)

2. 고려 사항

• 이전의 결과값을 저장하기 위해 메모이제이션하였으며, n이 11 이하이므로 재귀로 풀어보았다.
• 모든 테스트케이스는 max 케이스의 부분합이므로, n이 max일 때의 memo를 구한 후 케이스들의 결과를 memo의 인덱스로 접근한다.
• n이 1, 2, 3일 때를 고려해 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"));