[알고리즘/백준] 2193번 이친수 Python 파이썬

 

요즘도 여전히 다이나믹 프로그래밍 문제를 풀고 있습니다. 

 

 

이번 문제는 위 조건에서 요구하는 이친수를 찾는 문제입니다. 그러면 무엇을 해야하는가? 전번 풀이에도 이야기했듯이 다이나믹 프로그래밍 문제를 풀 때는 규칙성을 찾는 것이 매우 중요하며 이를 찾기 위해 직접 몇가지의 경우의 수를 적어보면서 어떻게 결과가 도출되는지 과정을 살펴보는 것이었습니다. 

 

그렇기 때문에 초반에 어떻게 결과가 도출되는지 아래와 같이 적어보았습니다.

 

 

위 풀이를 보면서 규칙성을 찾을 수 있게 되었습니다. 바로 전 2단계의 답 합이 다음 답이라는 것이었습니다. 즉 dp[i] = dp[i-1] + dp[i-2] 로 정의할 수 있습니다.

 

다음과 같은 코드로 통과하였습니다.

 

import sys
input = sys.stdin.readline

n = int(input())
dp = [1] * (n+1)

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

print(dp[n])

 

원래는 dp에 0 값을 넣어주고 dp[1] = 1 / dp[2] = 1 정의해주었는데 이 경우 시간초과 오류가 떠서 위에와 같이 애초에 1를 집어넣고 업데이트 해주었습니다.