[백준 2579] 계단 오르기

문제

N개의 계단을 규칙대로 올라서 마지막 계단을 밟는다.

한 번에 한 개, 두 개의 계단을 밟을 수 있으며 연속해서 세 개의 계단은 밟지 못한다.

시작점은 계단에 포함되지 않는다.

위의 규칙대로 마지막 계단을 밟았을 때 최댓값을 구하라.

 

입력

첫째 줄에 계단의 개수를 입력한다.

이어서 계단의 순서대로 계단을 밟았을 때 얻는 점수를 입력한다.

 

출력

계단을 다 올랐을 때의 최댓값을 출력한다.

---

접근

만약 5개의 계단이 있다고 했을 때 계단이 1개, 2개 있을 때의 최댓값을 구하였다. 즉 계단의 범위를 좁혀서 최댓값을 구하였고 이때 계단의 개수에 따라 경우의 수를 구했을 때 중복되는 인덱스들이 많았다. 따라서 이를 동적계획법으로 미리 저장해두고 좀 더 위에 있는 계단에서 이용하고자 하였다.

 

구현

계단에 대한 정보를 step에 저장하고 i 번째 계단까지의 최댓값을 저장할 리스트 dp를 0으로 초기화하였다.

N = int(input())
step = []
dp = [0 for _ in range(N)]
for _ in range(N):
    step.append(int(input()))

 

그래서 계단의 개수에 따른 최댓값을 구할 때 규칙을 찾았고 점화식으로 표현하면

dp[i-2] + step[i] or dp[i-3]+step[i-1]+step[i]가 되었다.

이를 각각 계단이 1, 2, 3일 때와 그 외로 설정한 것은 인덱스에러를 방지하기 위해서이다.

if N == 1:
    answer = step[0]
elif N == 2:
    answer = step[0] + step[1]
elif N == 3:
    answer = max(step[0] + step[2], step[1] + step[2])
else:
    dp[0] = step[0]
    dp[1] = step[0] + step[1]
    dp[2] = max(step[0] + step[2], step[1] + step[2])
    for idx in range(3, N):
        dp[idx] = max(dp[idx-2]+step[idx], dp[idx-3]+step[idx-1]+step[idx])

    answer = dp[N-1]

---

전체 코드

import sys
input = sys.stdin.readline

N = int(input())
step = []
dp = [0 for _ in range(N)]
for _ in range(N):
    step.append(int(input()))

answer = 0
if N == 1:
    answer = step[0]
elif N == 2:
    answer = step[0] + step[1]
elif N == 3:
    answer = max(step[0] + step[2], step[1] + step[2])
else:
    dp[0] = step[0]
    dp[1] = step[0] + step[1]
    dp[2] = max(step[0] + step[2], step[1] + step[2])
    for idx in range(3, N):
        dp[idx] = max(dp[idx-2]+step[idx], dp[idx-3]+step[idx-1]+step[idx])

    answer = dp[N-1]
print(answer)

 

계속해서 인덱스 에러가 발생하였는데

dp[2]를 ste[0] + step[2] or step[1] + step[2]로 설정하였는데 계단의 개수가 하나라면 step의 크기는 1개이므로 더 높은 수의 인덱스에 접근하기 때문에 인덱스 에러가 계속 발생하였다.