백준 / 계단 오르기 / 2579번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 계단 오르기 / 2579번 (실버 3단계)

문제 사이트: https://www.acmicpc.net/problem/2579

 

문제 설명

---

나의 풀이

n = int(input())

stairs = []

for _ in range(n):
    s = int(input())
    stairs.append(s)

cnt = 1
answer = stairs[0]

for i in range(1, len(stairs) - 2):
    if cnt == 2:
        cnt = 0
        continue
    if stairs[i] > stairs[i + 1] and cnt < 2:
        cnt += 1
        answer += stairs[i]
    elif stairs[i] < stairs[i + 1]:
        cnt = 0

answer += stairs[-1]

print(answer)

첫 풀이는 계단을 올라가면서 현재 계단과 다음 계단의 점수를 비교해 나가는 그리디 알고리즘을 사용해서 풀었다. 하지만 이 풀이는 시작점을 무조건 밟아야할 필요가 없는데 지키고 있는 풀이라서 틀렸다.

답안

n = int(input())

stairs = [0] * 301
dp = [0] * 301

for i in range(1, n + 1):
    s = int(input())
    stairs[i] = s

dp[1] = stairs[1]
dp[2] = stairs[2] + dp[1]

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

print(dp[n])

이 풀이는 DP(동적계획법)을 이용하여 dp[i] = max(dp[i - 3] + stairs[i - 1] + stairs[i], dp[i - 2] + stairs[i])의 식을 세워서 문제를 해결했다. DP풀이는 메모리도 많이 사용하면서 점화식을 세우는 과정이 복잡하다.

---

※ 알아야 할 것

https://newkimjiwon.tistory.com/175

[알고리즘] 동적계획법(Dynamic Programming)