백준 1003번 피보나치 함수 파이썬 코드 + 풀이

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

1003번: 피보나치 함수

dp = [0]*41
dp[0] = [1,0]
dp[1] = [0,1]
for i in range(2,41) :
    dp[i] = [dp[i-2][0] + dp[i-1][0] , dp[i-2][1] + dp[i-1][1] ]
    
for _ in range(int(input())) :
    n = int(input())
    print(dp[n][0], dp[n][1])

 

---

풀이

이 문제에는 처음부터 대놓고 피보나치 함수를 만드는 코드가 적혀있다

그래서 여기 적혀있는 재귀로 구현된 피보나치 함수를 그대로 사용하고 틀리는 사람이 많은데

이 문제를 잘 읽어보면 시간 제한이 0.25초 라고 적혀있다

즉 이 문제는 다이나믹 프로그래밍으로 풀어야한다 재귀함수를 쓰면 답은 맞는데 무조건 시간 초과가 뜬다

 

그렇다면 다이나믹 프로그래밍으로 어떻게 구현해야 할까?

일단 먼저 재귀로 구현한 코드를 통해 0부터 9까지의 결과를 한번 확인해보자  코드를 따로 적지는 않겠다

 

 10
 0
1 0
 1
0 1
 2
1 1
 3
1 2
 4
2 3
 5
3 5
 6
5 8
 7
8 13
 8
13 21
 9
21 34

 

이 결과들을 보면 뭔가 규칙성이 보인다

맞다 피보나치 함수와 똑같다 2부터는 n-1과 n-2의 각각 숫자의 출력 횟수를 합친 결과가 나오는 것이다

이 규칙성만 찾으면 어렵지 않게 문제를 풀 수 있다