[BOJ 파이썬] - 01타일 (1904번)

접근

1일때 1개 (1)
2일때 2개 (11, 00)
3일때 3개 (100, 111, 001)
4일때 5개 (1100, 0000, 1001, 1111, 0011)
n 번 째 순열을 잘 보면 n-1, n-2번 순열과 뭔지 모르게 닮았습니다.

또한 반대로 생각해보면 3자리 일때의 순열을 4자리로 만드려면 더할 수 있는 카드는 00은 불가능하니 1밖에 없습니다.
그리고 2자리 일 때의 순열을 2자리로 만드려면 01, 10, 11, 00 을 붙일 수 있는데 01, 10, 11은 이미 3자리 일때에 사용하고 있죠. 그래서 00을 붙여야만 4자리로 만들 수 있습니다.
즉, n자리의 순열을 만들기 위해서는 n-1의 순열에 1을 더한 순열들의 합과
n-2의 순열에 00을 더한 순열들의 합을 더하면 되겠습니다.
이것을 식으로 정리하면 n = n-1 + n-2가 됩니다.

풀이

import sys
n = int(sys.stdin.readline())
dis = [0] * (n + 1)
dis[1] = 1
if n > 1: dis[2] = 2

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

여담

저는 바텀-업 방식으로 풀었지만 재귀를 이용한 탑-다운 방식으로도 풀 수 있습니다.