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

※ 문제

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

 

※ 문제 유형

다아니믹 프로그래밍 (SILVER_3)

※ 나의 풀이

• 다아니믹 프로그래밍 풀이
• 2차원 DP
• 각 피보나치 숫자를 구하는 과정에서 0 호출 횟수 와 1 호출 횟수를 저장
• 피보나치 공식인 fibo(x) = fibo(x -2) + fibo(x - 1)를 이용해 호출 횟수를 누적 계산 
• DP 배열 구조 :  dp[i]  =  [0 호출 횟수, 1호출 횟수]

import sys

T = int(sys.stdin.readline())

cases = []
for _ in range(T):
    cases.append(int(sys.stdin.readline()))

# dp = [[0, 0]] * (40 + 1) X 
# -> 가변 객체를 담을 경우 같은 객체를 참조하므로,
# 한 요소를 변경하면 다른 요소들도 함께 변경된다.
# 따라서 가변 객체를 다루는 2차원 부터는 for 문으로 생성
dp = [[0, 0] for _ in range(40 + 1)]

for i in range(0, max(cases) + 1):
    if i == 0:
        dp[i] = [1, 0]
    elif i == 1:
        dp[i] = [0, 1]
    else:
        dp[i][0] = dp[i - 1][0] + dp[i - 2][0]  # 0 호출 횟수
        dp[i][1] = dp[i - 1][1] + dp[i - 2][1]  # 1 호출 횟수

for n in cases:
    print(dp[n][0], dp[n][1])

주의할 점

• 처음 시도 dp = [[0, 0]] * (40 + 1)
  • [0, 0]인 객체를 반복하는 방법으로, 가변 객체인 하나의 리스트를 참조하므로, 변경하면 다른 요소들도 함께 변경
  • 1차원 인경우 [0] * (40 + 1)은 숫자 0을 반복하는 방법인 숫자는 불변 객체이므로, 적합한 방법
• 두번째 시도 dp = [[0, 0] for _ in range(40 + 1)]
  • for 문을 사용해 가변 객체를 독립적으로 생성
  • 주석 참고