[python/파이썬] 백준 2193 이친수

알고리즘/python

ㅌㅇㄴ 2022. 7. 13. 13:26

[문제 출처]

2193번: 이친수

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않

www.acmicpc.net

[문제 풀이]

이 문제는 직접 이친수가 몇 개인지 세보는 과정을 통해서 규칙을 발견해 풀어야 한다.

n = 0 > 0개

n = 1 > 1개

n = 2 > 0 + 1 = 1개

n = 3 > 1 + 1 = 2개

100 101

n = 4 > 1 + 2 = 3개

1000 1001 1010

n = 5 > 2 + 3 = 5개

10000 10001 10010 10100 10101

...

n자리수의 이친수는 n-1자리 이친수의 개수와 n-2자리 이친수의 개수의 합이 된다.

import sys
input = sys.stdin.readline

n = int(input())

dp = [0,1,1]

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

print(dp[n])