728x90
1. 문제
피보나치 수열은 아래와 같이 표현된다.
1, 1, 2, 3, 5, 8, 13, 21, 34, ...
각 숫자는 앞의 두 숫자의 합으로 나타내는 것을 알 수 있다.
P와 Q 그리고 n이 주어질 때, P번째 피보나치 숫자를 Q로 나눈 나머지를 구하여라.
2. 입력
첫 번째 라인에는 정수 T개의 테스트 케이스가 주어진다.
각 테스트 케이스는 정수 P와 Q가 주어진다.
3. 출력
각 테스트 케이스마다 "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라는 입력값에대한 나머지를 출력해주기만 하면 된다.
728x90