백준 2193 이친수 (파이썬)

https://www.acmicpc.net/problem/2193

2193번: 이친수

n-1 이친수 중 맨 뒤가 0이면 n번째에는 뒤에 0, 1을 놓을 수 있고 

                   맨 뒤가 1이면 n번째에는 0만 놓을 수 있다

 

풀어보면 n은 3 이상부터 a[n] = 2 * a[n-2] + a[n-3]의 규칙을 보인다 

import sys

input = sys.stdin.readline

n = int(input())
if n == 1:
    print(1)
    sys.exit()
a = [0 for _ in range(n+1)]
a[1], a[2] = 1, 1

for i in range(3, n+1):
    a[i] = 2 * a[i-2] + a[i-3]

print(a[n])