[2193] 이친수 (Python)

[문제]

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

2193번: 이친수

---

알고리즘 분류는 다이나믹 프로그래밍 입니다.

 

1자리 이친수 : 1

2자리 이친수 : 10

3자리 이친수 : 100, 101

4자리 이친수 : 1000, 1001, 1010

...

이 과정을 거치면 점화식을 구할 수 있습니다.

---

[코드]

import sys

li = [1, 1]
for i in range(2, 91):
    li.append(li[i - 2] + li[i - 1])

N = int(sys.stdin.readline())
print(li[N - 1])

이 문제의 점화식은 N자리 이친수 = N - 2자리 이친수 + N - 1자리 이친수 입니다.