[ BOJ 1904 ] 01타일(Python)

문제

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])