[Baekjoon] 1904번 01타일

문제

요약

1 한개 타일과 00 두개 타일이 있을 때, n개의 타일로 만들 수 있는 이진수의 개수를 15746으로 나눈 나머지를 구하시오.

 

원본

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

 

 

풀이

import sys
input = sys.stdin.readline

n = int(input())

lst = [0, 1, 2]

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