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

문제 요약

각 계단에는 일정한 점수가 쓰여 있음 - 그 점수 얻음

1. 한 계단 / 두 계단씩 오를 수 있다

2. 연속된 세 개의 계단은 모두 밟아서는 안 된다

3. 마지막 도착 계단은 반드시 밟아야 한다

각 계단에 쓰여 있는 점수가 주어질 때 총 점수의 최댓값

 

 

풀이

DP로 풀 수 있다. 

'마지막 도착 계단은 반드시 밟아야 한다' 라는 조건 -> 도착지부터 생각하는 접근이 더 쉽다.

 

n번째 계단에 올라오기 위해서는 두 가지 경우가 있다.

1. n-1번째 계단에서 오는 경우

dp[n] = dp[n-3] + stairs[n-1] + stairs[n]

2. n-2번째 계단에서 오는 경우

dp[n] = dp[n-2] + stairs[n]

-> 이 중에서 더 큰 수가 dp[n]이 된다.

 

dp[n-3]이 있기 때문에 1, 2, 3번째의 dp는 초기화해주어야 한다.

 

n = int(input())
stairs = [0] * (n+1)

for i in range(1, n+1):
    stairs[i] = int(input())
dp = [0] * (n+1)
if n > 0:
    dp[1] = stairs[1]
if n > 1:
    dp[2] = stairs[1] + stairs[2]
if n > 2:
    dp[3] = max(stairs[1] + stairs[3], stairs[2] + stairs[3])

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

print(dp[n])

 

주의할 점

계단의 개수는 300 이하의 자연수이므로, 0과 1을 포함한다.

따라서 n > 0, n > 1, n > 2와 같은 조건문을 붙여주어야 했다. 

아래와 같이 풀었을 때는 런타임에러 (IndexError)가 났다.

n = int(input())
stairs = [0] * (n+1)

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

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

print(dp[n])