💡문제접근
- 피보나치 수열의 10000번째 원소까지도 입력값으로 받을 수 있었기에 일반적인 점화식과
append
로 접근하는 문제는 아니라고 생각해서 다른 방법을 생각하다가 나온 방법이 dp배열을 이용하는 방법과 재귀함수를 이용하는 방법 두 가지였다.
💡코드1
import sys
input = sys.stdin.readline
def fibonacci(X):
if X == 0:
return 0
elif X == 1 or X == 2:
return 1
else:
return fibonacci(X-1) + fibonacci(X-2)
seq = 1
T = int(input())
for i in range(T):
P, Q = map(int, input().strip().split())
result = fibonacci(P)
print("Case #" + str(seq) + ":", str(result % Q))
seq += 1
📌 피보나치를 재귀로 구현한 방법(시간초과(TLE)가 발생함)
💡코드2(메모리 : 35048KB, 시간 : 100ms)
import sys
input = sys.stdin.readline
dp = [0] * 10001
dp[1] = 1
dp[2] = 1
for i in range(3, 10001):
dp[i] = dp[i-1] + dp[i-2]
seq = 1
T = int(input())
for i in range(T):
P, Q = map(int, input().strip().split())
result = dp[P]
print("Case #" + str(seq) + ":", str(result % Q))
seq += 1
💡소요시간 : 7m