피보나치 함수
-
[백준] 피보나치 함수알고리즘/백준 2021. 8. 10. 16:51
문제 링크 풀이 0, 1의 갯수에 대한 규칙만 찾으면 된다. f(0) -> 1, 0 f(1) -> 0, 1 f(2) -> 1, 1 f(3) -> 1, 2 f(4) -> 2, 3 f(5) -> 3, 5 각 항목도 피보나치 수열처럼 n번째 값은 [n-2] + [n-1]이다. 조금 더 자세히 보면 0의 갯수는 직전 항목의 1의 갯수와 같다. 그러므로 1의 횟수를 기준으로 점화식을 만들고 값을 설정해놓으면 된다. 코드 #include int main() { int dp[41]{ 0, 1, 1 }; int T; scanf("%d", &T); for (int i = 3; i < 41; ++i) dp[i] = dp[i - 2] + dp[i - 1]; while (T--) { int N; scanf("%d", &N);..