BOJ 2579

Input

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

import sys
input = sys.stdin.readline

n = int(input())
score = [0]*301
for i in range(n):
  score[i] = int(input())
dp = [0]*301

배열을 생성할 때 웬만하면 백준에서 주는 최대값을 크기로 해주는게 좋다. 생각보다 IndexError 런타임 에러가 많이 나기 때문… 기본적인 경우로 코딩해놓고 히든케이스 때문에 index가 벗어날 수 있다.

DP

DP는 규칙을 찾고 코딩하다 내가 말리는 기분이다…

먼저 처음 접근 방식은 이랬음.

"""
규칙이 반복되는데 그 중 최대값 구하기 = DP
1. 연속적으로 1 / 2 계단만 오를 수 있음
2. 점수의 최대값

- 3개 이상 연속되지 않는 조합
- 그 중 최대값
"""

나름 규칙 찾고, 2중 중첩 반복문으로 케이스를 모두 비교해서 최대값을 찾아야 하나 싶었음. 나름 끝에서부터 접근하는 방식은 맞았다만, 문제는 시작점부터 어떤 계단을 밟을지 고르는 방법과 동일하게 도착점에서 어떤 계단을 밟고 왔나 고르는 방법으로 풀었다는 거다.

여기서 생각을 좀 틀어서, 처음부터 더해나가되 어떤 계단을 밟았는지 알고, 고를 수 있는 index부터 어떤 계단을 밟을지 골라야 한다는 거다. 결국 도착점에서 모든 케이스를 비교하는게 아니라, 올라가면서 전까지 밟아온 케이스를 비교하고 골라야 한다는 것.

그래서 먼저 가능한 케이스를 정의해둔다.

dp[0] = score[0]
dp[1] = dp[0] + score[1]
dp[2] = max(dp[0] + score[2], score[1] + score[2])

어, 첫번째 칸을 안 밟을 수도 있는데…! 라고 생각했지만 이후 규칙성을 반영해서 일반적인 케이스를 코딩하면 이미 3번째 계단에 있는 내가 첫번째를 안 밟는 케이스를 선택할 수도 있다.

이후 일반적인 케이스 코딩.

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

결국 점화식은 다음과 같다.

# 현재 칸을 밟는다는 가정 하에,
# 이전 칸을 밟은 경우:
	# 전전 칸을 밟았으면 안 됨
	dp[i-3] + score[i-1] + score[i]
	
# 이전 칸을 밟지 않은 경우:
	# 전전 칸까지 밟을 수 있음
  dp[i-2] + score[i]

위 2가지 경우 중에 max 값을 골라 저장하면 된다.

Output

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

print(dp[n-1])