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

[문제 출처]

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

2193번: 이친수

 

[문제 풀이]

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

n = 0 > 0개

x

 

n = 1 > 1개 

1 

 

n = 2 > 0 + 1 = 1개

10

 

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])