[백준] 2193번: 이친수 - python

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

2193번: 이친수

공부하다가 머리식힐겸 DP문제 한문제

 

항상 DP는 옆에 주석으로 패턴을 남기면서 풀면 잘 풀리는 것 같다.

 

간단히 패턴을 찾았다. 

n = int(input())

dp = [0] * 91
dp[1] = 1
dp[2] = 1
dp[3] = 2 #100 101
dp[4] = 3 #1000 1010 1001
dp[5] = 5 #10000 10100 10010 10001 10101 

for i in range(6, n+1):
    dp[i] = dp[i-1] + dp[i-2] 

print(dp[n])

 

완성