[백준] 9711번 피보나치

💡문제접근

• 피보나치 수열의 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