백준 (boj) 파이썬 - 1003 번 : 피보나치 함수

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

1003번: 피보나치 함수

 

 

 

 

 

 

 

---

 

 

문제 분류 : 다이나믹 프로그래밍 https://infinitt.tistory.com/246

알고리즘 - 다이나믹 프로그래밍 (Dynamic Programming)

 

 

 

피보나치 함수를 C++소스로 제공하고, 거기에 관련하여 0과 1이 출력된 횟수를 구하는 문제였다.

0과 1의 출력도 피보나치와 마찬가지로 같은 점화식이 세워진다.

점화식 : dp[i] = dp[i-1] + dp[i-2]

다만 0과 1이므로 (2가지 이므로) 2중 배열을 사용해주면 된다.

 

 

*정답 코드(Python)

T = int(input())
dp = [(1,0),(0,1),(1,1),(1,2)] + [(0,0) for _ in range(37)]   #문제에서 N은 40까지라고 나온다.

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