[C++] 1003번 피보나치 함수

[문제]

1003번 문제보기

 

[제출코드]

 

[풀이]

f(0) = 0

f(1) = 1

f(2) = f(1) + f(0) = 1 + 0

f(3) = f(2) + f(1) = { f(1) + f(0) } + f(1) = 1 + 0 + 1

...

 

재귀로 풀면 위처럼 이미 계산한걸 또다시 계산해야하므로 비효율적이다.

하지만 DP로 풀게 되면, f(0)과 f(1)의 결과만 배열에 저장해놓고 2이상의 n은 앞의 2개의 결과를 더해주기만 하면 되므로 훨씬 시간이 단축된다.

 

[이야기]

알고리즘을 배우기 전 DP를 몰라서 시간초과로 틀렸던 문제다. 그때는 다이나믹을 생각하지 않고 재귀로 해서 틀렸었다.