백준 1904. 01타일

1904번: 01타일

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이

www.acmicpc.net

우선 패턴을 파악해보면 된다.

피보나치 수열과 같은 패턴이 된다. 이를 dp를 이용하여 구현하면 된다.

단, 값이 갈수록 기하급수적으로 커지기 때문에 정수 값을 금방 넘어가버리므로 값을 넣을 때부터 15746으로 나눈 나머지를 넣어줘야 메모리 초과가 일어나지 않는다.

n = int(input())

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

for i in range(3, n+1):
	lst[i] = (lst[i-1] + lst[i-2]) % 15746
print(lst[n])

Why not?