[Python] 2193번 이친수

✏️ 문제

 

문제 파악

n이 1, 2, 3, 4, 5일 때 각각 dp[n]의 값을 구하면 쉽게 점화식을 구할 수 있다. 

그림을 그려보면 다음과 같다.

num 배열은 dp 배열 앞뒤 값의 차이를 담은 배열이다.

그림을 보면 다음과 같은 점화식이 나오는 것을 알 수 있다.

• num[n] = dp[n-1]
• dp[n] = dp[n-1] + num[n-1]

 

나중에 보니 dp 배열 자체가 피보나치 수열와 같았음... = 이 말은 즉 num 배열 필요 X..

 

 

알고리즘

• 다이나믹 프로그래밍 

 

코드

n = int(input())
num = [0, 1, 1]
dp = [1, 1, 2]

for i in range(3, n):
  num.append(dp[i-1])
  dp.append(dp[i-1] + num[i-1])

print(dp[n-1])