백준17175 - 피보나치는 지겨웡~ (DP) JS

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

문제는 피보나치 수열을 응용하여, input이 들어왔을 때 피보나치 수열이 몇 번 호출되는지를 묻는다.

 

먼저 문제에서 제시된 함수를 살펴봐야 하는데, 

fibonacci(n)이 호출되고 fibonacci(n-1)과 fibonacci(n-2)이 호출됨을 확인할 수 있다. 

(이때 n이 2 이하인 경우는 추가 호출이 없음을 인지해야 한다.)

 

즉 예를 들면 다음과 같다.

// input === 2
fi(2) 
fi(1) fi(0)
// => 총 3번 호출

// input === 3
fi(3)
fi(2) fi(1) 
fi(1) fi(0) // 이때 fi(1)와 fi(0)은 fi(2)에서 일어나는 호출
// => 총 5번

// input === 4
fi(4)
fi(3) | fi(2)
fi(2) fi(1) | fi(1) f(0) // 각각 fi(3), fi(2)에서 일어나는 호출
fi(1) fi(0) // fi(2)에서 일어나는 호출
// => 총 10번

// input === 5
fi(5)
fi(4) fi(3)
fi(3) fi(2) | fi(2) fi(1)
fi(2) fi(1) | fi(1) fi(0) | fi(1) fi(0)
fi(1) fi(0)
// => 총 15번

 

따라서 fibonacci의 배열은 아래처럼 구성된다고 볼 수 있는데,

해당 배열은  dp[i] = dp[i-1] + dp[i-2] + 1 을 만족하므로 해당 식을 점화식으로 수립할 수 있다.

 

const dp = [1,1,3,5,9,15]
// dp[i] = dp[i-1] + dp[i-2] + 1

 

소스 코드

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

function solution(data) {
  const dp = [1,1,3,5,9,15]
  
  for(let i = 6 ; i <= data ; i ++) 
    dp[i] = (dp[i-1] + dp[i-2] + 1) % 1000000007
  
  console.log(dp[data])
}

solution(input)