출처 | https://www.acmicpc.net/

코드

import sys

input = sys.stdin.readline

n = int(input())

dp = [0] * 1000001
dp[1] = 1
dp[2] = 2

for k in range(3,n+1):
    dp[k] = (dp[k-1] + dp[k-2]) % 15746

print(dp[n])

설명

• 해당 설명을 풀어보면, 피보나치 수열의 패턴이라는 것을 알 수 있다. 그 점을 참고해 작성하면 된다.

• 해당 부분 런타임 오류로 인해 고생좀 했다...