[Python] 백준 2193 이친수

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

2193번: 이친수

문제 해결

- 다이나믹 프로그래밍(dp)인 것은 쉽게 눈치 챌 수 있다.

- n자리 이친수 개수를 dp[n]으로 놓을 때 dp[n] = dp[n-1] + dp[n-2]임을 알아야 한다.

 

그림판으로 그리면

dp[n]=dp[n-1] + dp[n-2]임을 알 수 있다.

 

CODE

import sys
input= sys.stdin.readline

n = int(input())
dp = [0 for _ in range(91)]
dp[1] = 1 #한자리 수는 1 한개
dp[2] = 1 # 두자리는 10 한개 11은 안되므로
if n>2:
    for i in range(3,n+1):
        dp[i] = dp[i-1] + dp[i-2]
print(dp[n])