스파르탄 365 4주차 (3) 계단오르기

4주차

백준 2579번 계단오르기

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

💡 풀이 전 계획과 생각

첫번째 계단부터 차례대로 밟는 방법을 생각했는 데, 그러면 3번 조건을 지키기가 너무 어렵다.
예전에 풀었던 문제인데, 그 때는 DP에 대한 공부가 부족했던 상태였고, 현재 보니 어떻게 해야할지 느낌이 온다.

💡 풀이

import sys
input = sys.stdin.readline

n = int(input())
dp = [0 for _ in range(n+3)]
print(dp)
stairs = [0 for _ in range(n+3)]
for i in range(1, n+1):
    stairs[i] = int(input())

print(stairs)

dp[1] = stairs[1]
dp[2] = stairs[1] + stairs[2]
dp[3] = max(stairs[1] + stairs[3], stairs[2] + stairs[3])
print(dp)

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

print(dp[n])

막혔던 점과 고민

🧐 막혔던 점

• 3번 조건
  - 3번 조건의 의미는 마지막 계단을 기준으로 점화식을 작성하라는 뜻이었다!

👏🏻 알게된 개념과 소감

조건에서 점화식의 기준을 준다는 점을 알게됐다