728x90
문제 요약
각 계단에는 일정한 점수가 쓰여 있음 - 그 점수 얻음
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])728x90
