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

정답률이 생각보다 낮은 문제입니다,, 아마 피보나치를 재귀로 구하다가 시간초과가 많이 나서 정답률이 낮은 것 같네요!

피보나치는 동적 프로그래밍(Dynamic Programming) 방식으로 풀어야 쉽게 통과 될 걸로 보입니다.

(피보나치 DP 코딩에 대해 쓴 글입니다. https://yejun402.tistory.com/2)

---

Python Code

 

def dp(a, b):
    dp = [1,1]
    cnt = 0
    for i in range(2,b+1):
        if dp[i-1]+dp[i-2] > b:
            break
        dp.append(dp[i-1]+dp[i-2])
    dp = dp[1:]
    for i in dp:
        if a <= i <= b:
            cnt += 1
    return cnt

while True:
    a , b = map(int, input().split())
    if a == 0 and b == 0:
        break
    print(dp(a,b))

---

성공!

( input() 대신 sys.stdin.readline() 사용하면 20ms 더 단축 하실 수 있어요!)