[백준 6571번] 피보나치 수의 개수 (python)

문제링크 : https://www.acmicpc.net/problem/6571

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

while(True):
    a, b = map(int,input().split())
    if a == 0 and b == 0 :
        break
    cnt = 0
    for i in range(1, 1001) :
        if a <= dp[i] and dp[i] <=b:
            cnt+=1
    print(cnt)

 

피보나치 계산에 따라 수가 매우 커지므로 python으로 푸는 것이 용이한 문제이다.

C++로 풀 경우 문자열로 바꾸어서 계산할 필요가 있다.

 

이외에는 사전에 피보나치를 dp를 통해 미리 계산해놓고 입력받은 값에 대해 범위만 체크해서 카운팅해주면 된다.