[dp] 백준 #2579 계단 오르기

문제

https://www.acmicpc.net/problem/2579

풀이

n = int(input())
stairs = [0]
score = [0] * (n+1) #편하게 하려고 앞에 0 냅두고 한 칸 더 만듦

for _ in range(n):
  stairs.append(int(input()))

#print(stairs)
score[1] = stairs[1]
if n == 1:
  print(score[n])
elif n == 2:
  score[2] = max(stairs[1]+stairs[2], stairs[2])
  print(score[n])
elif n == 3:
  score[2] = max(stairs[1]+stairs[2], stairs[2])
  score[3] = max(stairs[1]+ stairs[3], stairs[2]+ stairs[3])
  print(score[n])
else:
  score[2] = max(stairs[1]+stairs[2], stairs[2])
  score[3] = max(stairs[1]+ stairs[3], stairs[2]+ stairs[3])

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

  print(score[n])

접근

마지막 계단은 무조건 밟아야 하고, 연속으로 3개의 계단을 밟을 수 없으므로
마지막 계단으로 갈 수 있는 방법은 2가지이다.

1. 마지막 계단 전 계단을 밟은 경우
2. 마지막 계단 전전 계단을 밟은 경우

1번의 경우 연속으로 3개의 계단을 밟을 수 없으므로 마지막 계단 전 계단 값 + 마지막 계단 전전전 계단까지의 최대값 + 마지막 계단 값 이다.
2번의 경우는 마지막 계단 전전 계단까지의 최대값 + 마지막 계단 값이다.
마지막 계단을 n번째 라고 할 때 다음과 같이 표현할 수 있다.(인덱스 1부터 시작이라고 할 때를 가정)

1. 최대값1[n] = 점수[n-1] + 최대값[n-3] + 점수[n]
2. 최대값2[n] = 최대값[n-2] + 점수[n]

최종적으로 최대값은 그 두 가지 방법의 최대값을 구하는 것이기 때문에 아래와 같이 표현할 수 있다.

최대값[n] = max(최대값1[n], 최대값2[n])

현재 값을 구하기 위해서는 그 전 값이 필요하기 때문에 DP(Dynamic Programming)으로 접근을 했다. 재귀 함수 호출식은 시간 초과가 일어날 가능성이 높기 때문에 단순 반복문을 사용하는 Bottom-up 형태로 구현함.

score[n] = max(score[n-3] + stair[n-1], score[n-2]) + stair[n]

근데 계속 런타임 에러로 IndexError가 나서 보니
n이 4보다 작은 경우들 각각에 대해 처리를 해주지 않았다.
각각의 경우는 그 뒤의 연산들이 index가 없어서 불가능하기 때문에 따로 처리해주어서 해결하였다.