[파이썬/python] 백준 1904번 : 01타일 (🥈3)

https://www.acmicpc.net/problem/1904

피보나치 수열(점화식) 형태이고 동적계획법을 이용하여 풀이한다.

 

답:

import sys
input = sys.stdin.readline

dp = [0,1]
n = int(input())
for i in range(n):
    dp.append((dp[-1] + dp[-2]) % 15746)
print(dp[-1])

기본적인 피보나치 수열의 형태를 이용하여 풀이하였다.

 

 

오답:

dp = [0,1]
n = int(input())
for i in range(n):
    dp.append(dp[-1] + dp[-2])
print(dp[-1] % 15746)

이렇게 풀면 시간 초과가 난다.

아무래도 1000000이라는 길이는 무척 길기 때문에, 배열에 값을 추가할 때 값에 %15746을 해 주어야 시간초과가 나지 않는다.