[백준/Python] 1003 피보나치 함수

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

 

 

사용 알고리즘: DP

 

 

 

- dp 배열 초기화

 

0 과 1 이 출력되는 횟수를 함께 구해줘야 하기 때문에 dp 배열을 2차원 배열로 만들고, N 의 최대 값이 40 이기 때문에 배열의 크기를 41로 만들었다. 

 

dp 값은 n 번째 피보나치 수를 계산할 때 0, 1 이 출력된 수이다.

dp = [[0, 0] for _ in range(41)] 
# [0이 출력된 수, 1이 출력된 수]
dp[0] = [1, 0]
dp[1] = [0, 1]

 

 

- 0 과 1 이 출력되는 횟수 구하기

 

입력받은 테스트케이스 수만큼 for 문을 돌면서 계산

 

fibonacci(n) = fibonacci(n-1) + fibonacci(n-2) 이므로

dp[n] = dp[n-1] + dp[n-2] 이 되는데, 2 차원 배열이므로

 

-> dp[j][0], dp[j][1] = dp[j-1][0] + dp[j-2][0], dp[j-1][1] + dp[j-2][1]

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

 

 

 

전체 코드

T = int(input())

dp = [[0, 0] for _ in range(41)]
dp[0] = [1, 0]
dp[1] = [0, 1]

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