[백준] 2193 - 이친수 - (python 파이썬)

문제링크 : https://www.acmicpc.net/problem/2193

2193번: 이친수

 

풀이과정 :

전형적인 dp 문제인데, 처음에는 그 과정도 안보이고 점화식도 안보여서 고생했다.

 

10으로 시작하면서 101부터 시작은 dp[i-2]와 개수가 같고 100부터 시작은 dp[i-1]과

 

개수가 같다. 그러므로 초기에 자리수가 1,2,3 인 경우만 설정값으로 넣어주고,

 

나머지는 점화식 dp[i] = dp[i-2] + dp[i-1] 로 풀면 된다.

 

dp = [0, 1, 1, 2] + [0]*87
length = int(input())
for i in range(4, length+1):
    dp[i] = dp[i-2]+dp[i-1]
print(dp[length])

 

답(이미지)

 

후기 : dp 문제인것만 알면 점화식 찾는것은 간단한 문제다.