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

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

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

1003번: 피보나치 함수

 

 

문제 해결 포인트

- DP

- 입력값(1~40) 에 따라 0과 1이 불린 횟수를 점화식을 이용하여 구할 수 있다

- 입력값 0은 0이 1회/1이 0회 불린다. 입력값 1은 0이 0회/1이 1회 불린다.

- 입력값이 2라면 f(2) = f(1) + f(0) 이므로 1이 한 번, 0이 한 번 불린다.

- 입력값이 3이라면 f(3) = f(2) + f(1) 이므로

   f(2) 실행시 1한 번, 0 한 번 불린 것과 1이 한 번 불린 것을 더하면 1이 2번 0이 1번 불린다.

 

- 이를 통하여 점화식을 도출할 수 있다.

i == 0 일 때, 0 1회, 1 0회

i == 1 일 때, 0 0회, 1 1회

i > 2 일 때, a(i) = a(i-2) + a(i-1)

 

작성 코드

import sys
input = sys.stdin.readline

T = int(input())  # test case
alist = [[1, 0], [0, 1]] + [[0, 0] for _ in range(39)]  #0 ~ 40까지 [0이 불린 횟수, 1이 불린 횟수] 초기화

for i in range(2, 41):  # i >= 2일 때, a(i) = a(i-1) + a(i-2) 점화식
    alist[i][0] = alist[i-2][0] + alist[i-1][0]
    alist[i][1] = alist[i-2][1] + alist[i-1][1]

for _ in range(T):
    n = int(input())  # 각 요청에 따라 결과값 출력
    print(alist[n][0], alist[n][1])

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚