[ BOJ 2193 ] 이친수(Python)

문제

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])