백준 1003 - 피보나치 함수

문제

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

 

 

 

 

풀이

# 백준 / 실버3 / 피보나치 함수


import sys

dp = [0] * 41

dp[0] = 1
dp[1] = 1

for i in range(2,41):
    dp[i] = dp[i-1] + dp[i-2]


for _ in range(int(sys.stdin.readline())):
    n = int(sys.stdin.readline())
    
    if n == 0 :
        print(dp[0],0)
    elif n == 1:
        print(0, dp[1])
    else:
        print(dp[n-2], dp[n-1])

 

그냥 피보나치를 구현하면 풀리지 않음

 

dp를 이용하는데 문제에서는 0의 출력 횟수, 1의 출력 횟수를 구하는 것

 

그렇다면 n일때 n-1의 0,1 출력 횟수 + n-2 일때의 0,1 출력 횟수를 더하면 나온다.

 

하지만 그냥 피보나치 수열을 구한 후 n-1, n-2를 출력해줘도 정답이 맞았다.. (ex . 0,1,1,2,3 일 때, n==2 라면 답은 1,2가 된다. + 첫번째 시작은 1로 설정했다.)

 

정석 풀이는 앞서 말했듯 n일때 0의 출력 횟수 = n-1일때의 0의 출력 + n-2일때의 0의 출력 이 될 것이다.