백준 1904번: 01타일 python

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

문제 접근

타일의 개수 N 이 주어졌을 때 만들 수 있는 2진 수열의 개수를 15746으로 나눈 나머지를 출력해야한다.

타일은 '1'또는 '00'을 사용해야한다.

즉
N=1, 1만 만들 수 있고 , f(1) = 1
N=2는 11또는 00 두가지 가능하고, f(2) = 2
N=3일때는 100, 001 , 111 이렇게 세가지만 가능하고, f(3) = 3
N=4일때는 0000, 0011, 1001, 1100, 1111 이렇게 다섯 가지가 가능하다. f(4) = 5

아직 왜 15746으로 나눈 값을 출력해야하는지는 모르겠다만 규칙은 보인다.

어떤 길이 N의 문자열을 만드는 경우의 수는 다음 두 가지 방식으로 만들 수 있다
f(N) =
1. 길이 N-1에서 앞에 "1"을 붙이는 경우 → 경우의 수 = f(N-1)
2. 길이 N-2에서 앞에 "00"을 붙이는 경우 → 경우의 수 = f(N-2)
를 더해주면 된다.

즉 f(3)은
f(2) 11 , 00 앞에 1을 붙인 '111', '100' 와
f(1) 1 앞에 00을 붙인 '001' 을 가진다.

즉 이 문제는, f(N) = f(N-1) + f(N-2) 점화식을 가진 피보나치 수열이다.

해답

import sys
n = int(sys.stdin.readline())

dp = [0] * (n + 2) # n+1 일 경우 n=1일때 dp=[0]*2 인데 그럼 dp[2] = 2 할당에서 에러가남
dp[1] = 1
dp[2] = 2

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

print(dp[n])