[BOJ / Python] 2193 이친수

🔑 문제 

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

 

 

🔐 풀이 방법

dp를 이용해서 풀자 !

 

🤹 점화식 구하기 

1: 1 -> 1가지 방법

2: 10 -> 1가지 방법

3: 100 101 -> 2가지 방법

4: 1010 1001 1000 -> 3가지 방법

5: 1000 10101 10100 10010 10001 -> 5가지 방법

…

…

…

 

전 단계의 이친수 개수와 전전단계의 이친수 개수를 합하면 현재 단계의 이친수가 나온다.

dp[i] = dp[i - 1] + dp[i - 2]

 

 

👑 전체 코드 

# https://www.acmicpc.net/problem/2193
# 이친수

import sys
input = sys.stdin.readline

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

print(dp[n])