계단 오르기 [백준 2579](파이썬)

문제

---

계단 오르기 [백준 2579]
https://www.acmicpc.net/problem/2579

풀이

---

이런 류의 문제는 다이나믹 프로그래밍으로 풀어야하는데 세개의 연속된 계단을 못 오른단 것에서 고전을 하였다.

• 연속해서 얼마나 계단을 올랐는지 저장하는 변수 이용
• 점화식 : dp[i] = max(dp[i-2]+point[i], dp[i-1]+point[i])

하지만 왜인지 계속해서 오답이 떴었고 다른 분의 코드를 참고하니 점화식에서 차라리 dp[i-3]+point[i-1]+point[i] 연속해서 두번 내려가는 거랑 비교하는 거를 볼 수 있었다.

코드

---

N = int(input())
# dp에 사용할 배열과 각 계단에 저장할 값을 선언
dp = [0] * (N+1)
point = [0] * (N+1)
for i in range(1, N+1):
    point[i] = int(input())
if N==1:
    print(point[1])
    exit()
elif N==2:
    print(sum(point[:3]))
    exit()
dp[1] = point[1]
dp[2] = point[1]+point[2]
for i in range(3, N+1):
    dp[i] = max(dp[i-2]+point[i], dp[i-3]+point[i-1]+point[i])

print(dp[-1])