[백준] 2579번 계단 오르기

💡문제접근

• 각 계단에서 얻을 수 있는 점수의 최댓값의 경우를 예시를 들어 나눈 후에 점화식을 세웠다.
• 4번째 계단에 도착했을 때 얻을 수 있는 점수의 최댓값을 아래와 같이 경우를 나누어 생각해보았다.

①. 1번째 계단을 밟고 그 다음 3번째 계단을 밟고 그 다음 4번째 계단을 밟은 경우

②. 2번째 계단에 있는 상태(이 때 2번째 계단에서 얻을 수 있는 점수의 최댓값은 1번째 계단을 밟고 2번째 계단을 밟은 경우)에서 바로 4번째 계단을 밟은 경우

• 위의 두 가지 경우를 일반화하여 점화식을 세워 코드를 작성했다.

• 질문게시판 답변
  Q. max(score)는 불가능하고 score[N]는 가능한 이유
  A. 마지막 계단을 무조건 밟아야 한다는 조건 때문이다. 마지막 계단을 밟지 않으면 최댓값이 되는 경우가 존재할 수 있기 때문이다.

💡반례

입력

4
30
40
100
1

출력

131

• 4번째 계단은 무조건 밟아야 한다. 경우를 두 가지로 나누어보면 다음과 같다.
  ①. 1번째 계단 → 3번째 계단 → 4번째 계단 : 30 + 100 + 1 = 131
  ②. 2번째 계단 → 4번째 계단 : 70 + 1 = 71

💡코드(메모리 : 30616KB, 시간 : 48ms)

N = int(input())
stair = [0] * 301
score = [0] * 301

for i in range(1, N+1):
    stair[i] = int(input())

score[1] = stair[1]
score[2] = stair[1] + stair[2]
score[3] = max(stair[3] + stair[1], stair[3] + stair[2])
for i in range(4, N+1):
    score[i] = max(stair[i] + stair[i-1] + score[i-3], stair[i] + score[i-2])
print(score[N])

💡소요시간 : 43m