글 읽기 - 시간문제

(追記) (追記ここまで)

2749번 - 피보나치 수 3

일단 실행을 시켜봤습니다 그랬는데 엄청난 문제가 생겼습니다 바로 시간 문제였습니다 1000을 넣어도 오래걸립니다 대략 제가 계산한건 O(n)인데 이거도 뭔가 잘못 된것 같습니다 이렇게 쉽게 안 풀릴껄 알고있었지만 시간 복잡도 계산이 잘못된걸까요?

def fib(n):
 while True:
 if n==0:
 return 0
 elif n==1:
 return 1
 else:
 return fib(n-1)+fib(n-2)
N=int(input())
print(fib(N))

2747번이나 2748번이 그런 풀이법이고 이 문제는 괜히 골드가 아닙니다. 다른 방식으로 접근해야 됩니다.

분할 정복 키워드로 한번 접근해보세요.
피보나치에 대한 분할 정복은 이항 계수로 풀어 쓸 수 있다고 합니다.

다들 진짜 감사합니다

댓글을 작성하려면 로그인해야 합니다.

(追記) (追記ここまで)

Baekjoon Online Judge