2579번: 계단 오르기

🔗 문제 ∙ 2579번 : 계단 오르기

문제

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 계단에는 일정한 점수가 쓰여있고 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.
계단을 오르는데는 다음과 같은 규칙이 있다.
1. 계단은 한 번에 한 계단 혹은 두 계단씩 오를 수 있다. 즉, 한 계단을 밟고 다음 계단이나 다다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아햐 한다.
각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최대값을 구하는 프로그램을 작성하시오.

입력

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

출력

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

🔑 풀이

포도주 시식 문제와 거의 동일한 문제이다.

• 각 계단의 지점에서 가능한 이전 단계를 생각해보면 된다.

현재 4번째 계단인 25에 있다고 가정해보자. 25로 올라올 수 있었던 위치는

• 1) 3번째 15
• 2) 2번째 20

지점이 된다.
1) 만약 아래와 같이 3번째 계단에서 올라왔다면, 그 3번째 계단은 1번째 계단에서 올라왔을 것이다.
연속된 3개 계단을 올라올 수 는 없기 때문에, 1번째 -> 3번째 -> 4번째의 경우만 가능하다.

이를 점화식 세워보면 아래와 같다.

dp[i] = dp[i-3]+ arr[i-1]+ arr[i]

2) 두 번째 아래인 2 단계에서 올라온 경우를 생각해보자.

여기서 dp[2]는 2 단계로 올라올 때까지 얻을 수 있었던 최대 점수를 의미 한다. arr[2] 값과는 다르게 해당 단계로 오기까지의 값들을 모두 포함한다. 이를 점화식으로 살펴보면 아래와 같다.

dp[i] = dp[i-2]+arr[i]

매 단계에서 위의 두 가지 경우가 나오기 때문에, 두 값 중 최대 값을 선택하면서 도착지점까지 올라간다.

코드

N = int(input())
arr = [0]
dp = [0] * (N+1)
for _ in range(N):
    arr.append(int(input()))


for i in range(1, N+1):
    if i == 1:
        dp[i] = arr[1]
    elif i == 2:
        dp[i] = arr[1]+arr[2]
    else:
        dp[i] = max(dp[i-3]+arr[i-1]+arr[i], dp[i-2]+arr[i])

print(dp[N])