백준1003 - 피보나치 함수 (DP) JS

https://www.acmicpc.net/problem/1003

해당 문제는 이전 포스팅과 같이, 문제가 요구하는 것에 규칙성(점화식)을 찾아 해결하면 된다. 

2023.10.10 - [개발/algorithm] - 백준17175 - 피보나치는 지겨웡~ (DP) JS

 

0부터 6까지의 0, 1의 등장 횟수를 구하면 다음과 같다.

0 => 1 0
1 => 0 1
2 => 1 1 / f(2)는 f(1), f(0)을 호출하기 때문에 각각 한번씩이다
3 => 1 2 / f(2), f(1) | f(1), f(0) 을 호출한다 // 이때 f(1), f(0)는 fi(2)에서 호출
4 => 2 3 / fi(3), f(2) | f(2) f(1) f(1) f(0) | f(1) f(0)
5 => 3 5 // 중략
6 => 5 8

그리고 n > 1 일 때, 0과 1 모두 피보나치 수열과 같은 형태로 증가하고 있음을 확인할 수 있고,

그리하여 다음과 같은 형식으로 테이블을 구현할 수 있다.

const dp = {}
dp[0] = [1,0]
dp[1] = [0,1]
  
for(let i = 2 ; i <= 40 ; i ++) {
  const [a1,b1,a2,b2] = [...dp[i-2], ...dp[i-1]]
  dp[i] = [a1+a2, b1+b2]
}

 

소스 코드

const fs = require('fs')
const input = fs.readFileSync(process.platform === "linux" ? "/dev/stdin":"입력.txt")
  .toString().trim().split('\n')

function solution(data) {
  data.shift()
  const dp = {}
  dp[0] = [1,0]
  dp[1] = [0,1]
  
  for(let i = 2 ; i <= 40 ; i ++) {
    const [a1,b1,a2,b2] = [...dp[i-2], ...dp[i-1]]
    dp[i] = [a1+a2, b1+b2]
  }
  
  const result = data.map(el => dp[el].join(' '))
  console.log(result.join('\n'))
}

solution(input)