백준 - 9711번 피보나치(DynamicProgramming, Silver3, Python)

문제

피보나치 수열은 아래와 같이 표현된다.

1, 1, 2, 3, 5, 8, 13, 21, 34, ...

각 숫자는 앞의 두 숫자의 합으로 나타내는 것을 알 수 있다.

P와 Q 그리고 n이 주어질 때, P번째 피보나치 숫자를 Q로 나눈 나머지를 구하여라.

입력

첫 번째 라인에는 정수 T개의 테스트 케이스가 주어진다.

각 테스트 케이스는 정수 P와 Q가 주어진다.

출력

각 테스트 케이스마다 "Case #x: M" 형식으로 출력한다.

x는 테스트 케이스 번호(1부터 시작), M은 P번째 피보나치 숫자를 Q로 나눈 나머지이다.

---

풀이

import sys

input = sys.stdin.readline

t = int(input())

fibo_dp = [0] * 10000
fibo_dp[0] = 1
fibo_dp[1] = 1
fibo_dp[2] = 2

for i in range(3, 10000):
    fibo_dp[i] = fibo_dp[i-1] + fibo_dp[i-2]


for j in range(t):
    p, q = map(int, input().split())

    print("Case #{}:".format(j+1), (fibo_dp[p-1] % q))

---

피보나치 수열을 dp 배열을통해 생성하고, 문제의 요구사항에 따라 q라는 입력값에대한 나머지를 출력해주기만 하면 된다.