2579. 계단 오르기

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

 

 

 

계단	0	1	2	3	4	5
점수	10	20	15	25	10	20

 

 

 

예시를 그대로 갖고왔다.

5번째 계단은 무조건 밟아야 한다.

그럴 때 최댓값은, 5번째 계단의 점수 20을 더한 상태에서 

4번째 계단을 선택했을때이거나

3번째 계단을 선택했을 때이다.

 

4번째 계단을 선택하려면 3번째 계단은 선택하면 안 된다. (3개 연속 밟을 수는 없으므로)

3번째 계단을 선택하려면 2, 1번째 계단 중 어떤 것을 선택해도 상관 없으며 최댓값을 고르면 된다. 

 

val은 바로 전 계단을 선택했을 때의 최댓값을 R, 

전전 계단을 선택했을 때의 최댓값을 F로 해서 두 값을 모두 담았다. 나중에 최종적으로 둘 중에 최댓값을 고를 것이다.

 

이를 정리해보면

 

N번째 계단에서의 최댓값은 일단 N번째 점수를 더한 상태에서 (stair[col])

N-1번째를 선택하되 N-1은 바로 전 계단이 아닌 전전 계단을 선택한 상태거나 (val[col-1][F])

N-2번째를 선택하고 N-2가 바로 전 계단을 선택했거나, 전전 계단을 선택했을때의 두 점수 중에서 최댓값을 고르는 것이다. (max(val[col-2][F], val[col-2][R])

 

쉽게 설명하면 F는 Front로 "앞에꺼, 즉 -2번째 계단을 선택한 상태" , R은 "뒤에꺼, 즉 -1번째 계단을 선택한 상태"로 보면 된다.

 

내가 풀었지만, F, R이라는 단어를 잘못 선택한 것인지 쉽게 설명하기가 영 어렵다.

그림 그리면서 F는 전전 거를 선택한 상태, R은 전 거를 선택한 상태라고 생각하면 조금이나마 쉽다..

미래의 나에게 하는 이야기.

 

 

import sys


def solve():
	dp = []
	dp.append([stair[0], stair[0]])  # dp[0]

	for i in range(1, N):
		if i == 1:
			dp.append([stair[0]+stair[1], stair[1]])
		else:
			walk = dp[i-1][JUMP] + stair[i]
			jump = max(dp[i-2]) + stair[i]
			dp.append([walk, jump])
				
	print(max(dp[N-1]))


WALK, JUMP = 0, 1  # 그 전 계단을 걸어온경우, 점프한경우
input = sys.stdin.readline
N = int(input())

stair = [int(input()) for _ in range(N)]

solve()