[Python] 백준 2193_ 이친수

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

이 문제는 다이나믹 프로그래밍(DP)을 이용하여 해결할 수 있는 문제이다.

1. DP정의

• 이친수는 0으로 시작하지않으므로 d[0]=1
• 이친수에서 1은 두 번 연속으로 나타나지 않으므로 d[0]=1
  

2. 점화식 찾기

따라서 d[i] = d[i-1]+d[i-2] 라는 점화식을 찾을 수 있다.

3. 코드

import sys
input = sys.stdin.readline

n= int(input())

#dp정의 - d[0],d[1]=1 (첫자리는 무조건 1, 두번째자리는 무조건 0) 1가지씩
d = [1]*n

for i in range(n):
    if i==0:
       d[i]=1
    elif i ==1: 
       d[i]=1      
    else:
        d[i]=d[i-1]+d[i-2]

print(d[n-1])