[1904] 01타일 (Python)

[문제]

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

1904번: 01타일

---

알고리즘 분류는 다이나믹 프로그래밍 입니다.

 

N	2진 수열	개수
1	1	1
2	00, 11	2
3	001, 100, 111	3
4	0000, 0011, 1001, 1100, 1111	5
5	00001, 00100, 10000, 00111, 10011, 11001, 11100, 11111	8

이 과정을 거치면 점화식을 구할 수 있습니다.

---

[코드]

import sys

li = [1, 2]
for i in range(2, 1000000):
    li.append((li[i - 2] + li[i - 1]) % 15746)

N = int(sys.stdin.readline())
print(li[N - 1])

이 문제의 점화식은 N = N - 2 + N - 1 입니다.