백준 2579번 계단오르기 [Python]

[Silver III] 계단 오르기 - 2579

문제 링크

성능 요약

메모리: 31120 KB, 시간: 40 ms

분류

다이나믹 프로그래밍

제출 일자

2024년 3월 23일 10:19:29

문제 설명

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

<그림 1>

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.

<그림 2>

계단 오르는 데는 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

풀이

import sys
input = sys.stdin.readline

N = int(input())

step = [0]*301
for i in range(1, N+1):
    step[i] = int(input())

dp = [0]*301
dp[1] = step[1]
dp[2] = step[1] + step[2]
dp[3] = max(step[1], step[2]) + step[3]

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

print(dp[N])

DP로 접근하는건 인지했지만 코드를 구현하는데 있어 아직은 감이 덜 잡혔다고 느꼈다. 최대한 코드를 보지 않고 어떤 흐름으로 동작을 하는지만 이해를 한 후에 구현하려고 시도했다. 처음 문제를 봤을 때, 시작점에서 어떻게 이동을 해야 도착지에 도달함과 동시에 최대값을 도출할 수 있을까를 고민했다. 하지만 문제를 다르게 접근해보면 도착지점에 도달하기 직전 위치에서의 이동방법부터 생각을 해보면 좀 더 쉽게 이해할 수 있었다. 도착지점에 도달하기 전의 위치는 위의 그림을 예시로 들었을 때,다음과 같이 2가지 방법이 있다.

1. 4번 계단에서 2칸 이동하는 방법
2. 5번 계단에서 1칸 이동하는 방법

이 2가지 방법의 원리를 이해하면 각각 누적된 값을 비교하여 최대값을 도출할 수 있게된다. 코드에서는 1~3계단까지의 누적값을 dp리스트에 저장했고 4번부터 N까지 순차적으로 이전 dp값들을 이용하여 최대값을 도출한다.

번외로 계단리스트의 크기와 dp리스트의 크기를 입력받은 N의 크기로 동적 할당을 시도했는데, 런타임에러가 떴다. 알고보니 dp의 크기를 넉넉하게 주지 않은 것이 문제였다. 문제에서 입력은 300이하의 자연수였는데 만약 여기서 N을 1로 설정한다면 dp를 1 부터 3까지 초기화 하는 과정에서 인덱스의 범위가 벗어나게 된다. 인덱스의 범위를 잘 생각해야 할 것 같다.