[Python] 알고리즘/Silver
[2193] 이친수 (Python)
-Becca-
2021. 11. 15. 18:09
[문제]
https://www.acmicpc.net/problem/2193
2193번: 이친수
0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않
www.acmicpc.net
알고리즘 분류는 다이나믹 프로그래밍 입니다.
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자리 이친수 입니다.