백준 2579번: 계단 오르기 (Python)

접근

단계별 문제에서 동적 계획법 이전 문제들과 비슷한 문제이다.

2021.03.27 - [SW/백준 (Python)] - 백준 1149번: RGB 거리 (Python)

백준 1149번: RGB 거리 (Python)

2021.03.28 - [SW/백준 (Python)] - 백준 1932번: 정수 삼각형 (Python)

백준 1932번: 정수 삼각형 (Python)

그런데 문제에서 말하는 내용이 헷갈려서 여러 번 수정하며 진행하였다. 특히 연속해서 두 개까지는 밟아도 되는 줄 알고 조건을 무지하게 많이 넣었다가 답이 다르게 나오는 것을 보고 다시 수정하였다.

n번번째 요소에 [직전 단계에 두 계단을 한번에 올라온 max 값, 직전 단계에 한 계단 올라온 max 값]을 요소로 갖는 max_stair 리스트를 작성하여 문제를 해결할 수 있다.

for j in range(2, n + 1):
    max_stair[j][0] = max(max_stair[j - 2]) + stair[j]  # 두 계단 전 값들 중 max + 현재 계단 값
    max_stair[j][1] = max_stair[j - 1][0] + stair[j]  # 한 계단 전 값들 중 0번 요소 + 현재 계단 값

각 계단에서의 max 값은 두 값중 max 값을 통해 구할 수 있다.

코드

import sys

n = int(sys.stdin.readline())
max_stair = [[0, 0] for _ in range(n + 1)]  # 각 요소는 0번 요소로 두 칸 올라온 max, 1번 요소로 한 칸 올라온 max를 가진다.
stair = [0 for __ in range(n + 1)]
for i in range(1, n + 1):
    stair[i] = int(sys.stdin.readline())
max_stair[0] = [0, 0]
max_stair[1] = [stair[1], stair[1]]
if n > 1:
    for j in range(2, n + 1):
        max_stair[j][0] = max(max_stair[j - 2]) + stair[j]
        max_stair[j][1] = max_stair[j - 1][0] + stair[j]
print(max(max_stair[-1]))

더 생각해 볼 것?

...