[백준/DP] 2193 이친수 (Python, 파이썬)

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

2193번: 이친수

 

문제의 조건

- 0과 1로만 이루어진 수를 이진수라고 한다.

- 다음 조건을 만족하면 이친수라고 한다.

  1. 이친수는 0으로 시작하지 않는다

  2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

- N자리 이친수의 개수를 구하는 문제

 

d = [0]*91
n = int(input())
d[1] = 1
d[2] = 1
for i in range(3, n+1):
    d[i] = d[i-1] + d[i-2]
print(d[n])