백준 2193 이친수

과정

• DP.
• 초기 4 단계까지 구해보면
• 1 - 10 - 100, 101 - 1000, 1001, 1010 - 10000, 10001, 10010, 10100, 10101
• 이친수는 10으로 시작해야한다.
• 길이가 i인 이친수는 3째자리부터 마지막자리까지 값을 i-1과 i-2에서 구할 수 있다.
• 10로 시작하므로 0과 1 두 수로 시작하는 수가 뒤에 올 수 있다. 0으로 시작하는 값은 i-1에서, 1로 시작하는 값은 i-2에서 찾을 수 있다.

N = int(input())
dp = [0] * (N+1)
for i in range(1, N+1):
    if i == 1:
        dp[1] = 1
    elif i==2:
        dp[2] = 1
    else:
        dp[i] = dp[i-1] + dp[i-2]
print(dp[-1])