https://www.acmicpc.net/problem/1904
01타일 분명히 어려웠는데..
냅색 풀다가.. 이제 보니 선녀같다.
점화식만 세우면 금방 풀 수 있다.
d(n) = 타일 크기가 n일 때, 만들 수 있는 가짓수
d(0) = 0
d(1) = 1 (1)
d(2) = 2 (00,11)
d(3) = 3 (001, 100, 111) = d(2) + 1
d(4) = 4 (0011, 1100, 1111, 1001) = d(3) + 1
타일의 크기가 n일 때, d(n-1) 에서 늘어날 수 있는 가짓수는 한가지밖에 없다.
왜냐하면 길이가 1일 타일은 [1] 밖에 없기 때문이다.
import sys
input = sys.stdin.readline
n = int(input())
dp = [0 for _ in range(n+1)]
dp[1] = 1
dp[2] = 2
for i in range(3,n+1):
dp[i] = ((dp[i-1] % 15746) + (dp[i-2] % 15746)) % 15746
print(dp[n])