https://www.acmicpc.net/problem/2193
n개의 자릿수에 대한 이친수 개수 구하기~
2xn 타일링 문제와 동일하게 겹치는 경우의 수를 제외하고 세주면 된다.
dp[i]
= i 자리의 이친수 개수
1. 첫번째 자리는 반드시 1로 시작한다.
2. 연속으로 1이 올 수 없으니 두번째 자리는 반드시 0이다.
dp[1] = 1 (1)
dp[2] = 1 (10)
dp[3] = 2 (101, 100)
dp[4] = 3 (1000, 1001, 1010) ...
dp[n]
=
dp[n-1] + (0)
+
dp[n-2] + (01)
import sys
input = sys.stdin.readline
n = int(input())
dp = [0] * (n+1)
if n < 3:
print(1)
else:
dp[1] = 1
dp[2] = 1
# n-1 이친수에 0 을 추가한 경우 + n-2 이친수에 01을 추가한 경우
for i in range(3,n+1):
dp[i] = dp[i-2] + dp[i-1]
print(dp[n])