https://www.acmicpc.net/problem/2579

🥚문제

---

🥚입력/출력

---

🍳코드

n = int(input())
dp = [[0]*(n+1) for _ in range(n+1)] #2*2 matrix
scores = [0] + [int(input()) for _ in range(n)]

# base case 설정
dp[1] = scores[1]
if n >= 2:
    dp[2] = max(scores[1] + scores[2], scores[2])
if n >= 3:
    dp[3] = max(scores[1] + scores[3], scores[2] + scores[3])

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

---

🧂아이디어

• 어려웠다... 나름 dp 감을 잡았다고 생각했는데 이번껀 쉽게 떠오르지 않아 다른 분들 블로그를 참고했다.
• 게다가 테스트케이스가 교묘했던게, 틀린 방법으로 풀어도 항상 75가 나오더라!🙄
• 스스로 다른 분들 코드를 보고 정리한 아이디어를 첨부한다.
• (i-1)번째 계단을 밟고, (i)번째 계단을 밟는 경우를 못 떠올렸다.