Baekjoon Training #1904

---

#1904 01타일

import sys
input = sys.stdin.readline

n = int(input())
dp = [0] * 1000001
dp[1] = 1
dp[2] = 2

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

DP 문제인 만큼 발상이 중요했다.

DP[1] = 1 ( 1 )

DP[2] = 2 ( 11 , 00 )

DP[3] = 3 ( 111, 100, 001)

DP[4] = 5 ( 1111, 1100, 1001, 1100, 0000 )

위의 특징을 보고 피보나치와 유사하다는 생각을 떠올렸다. 그후에 검증과정을 거쳐 DP[n] = DP[n-1] + DP[n-2]임을 알게 되었다. 그 이유는 n번째 DP는 n-1번째 2진수들에 1을 붙이고 n-2번째 2진수들에 00을 붙이는 방식으로 만들 수 있기 때문이다. 이러한 특징은 숫자를 구성하는 단위가 00과 1이 유일하기 때문이다. 11이 불가능 한 것은 n-1번째 2진수가 만들어질때 1을 붙인 경우가 있고 거기에 1을 붙이면 n-2번째 2진수에 11을 붙이는 경우를 전부 커버할 수 있기 때문이다.

---