계단 오르기 백준 2579번 DP

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

문제 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.

계단 오르는 데는 다음과 같은 규칙이 있다.

• 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.

• 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
• 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

이번에는 계단 오르기 문제입니다. 마찬가지로 지금 상태를 구하기 위해서는 이전 상태의 값을 구해야하고 그중에서 최대가 되는 값을가지고 갱신해나가면 됩니다.

조건에서 한계단씩 또는 두계단씩 오를 수는 있지만 연속해서 세 개의 계단을 밟을수는 없다고 합니다. 즉 한번 한칸 오르기를 연속해서 두번할 수 없다는 제약 조건이 들어가게 됩니다.

그러면 이렇게 생각해볼 수 있습니다. 이전에 한칸을 오르지 않았을때 한칸오르는것과 어느 상황에서도 상관없는 두칸오르기로 올라가는 방법 그리고 그중 큰 것을 선택하면 됩니다.

import sys

num = int(input())
stairs = [0]*(num+1)
for i in range(1,num+1):
    stairs[i] = int(input())
    
if num==1:
    print(stairs[1])
    sys.exit()

dp = [[0]*(num+1) for _ in range(3)]
dp[1][1] = stairs[1]
dp[2][1] = 0
dp[1][2] = stairs[2]
dp[2][2] = stairs[1] + stairs[2]

for i in range(3,num+1):
    dp[1][i] = max(dp[1][i-2], dp[2][i-2]) + stairs[i]
    dp[2][i] = dp[1][i-1] + stairs[i]
    
print(max(dp[1][num],dp[2][num]))

인덱스를 편리하게 하기 위해서 크기를 1씩 더 키웠습니다. dp[1][n]에는 한칸 올라갔을때의 점수를 dp[2][n]은 두칸 올라갔을때의 점수를 기록합니다.

첫번째 한칸오르기에서는 현재 위치의 점수와 두칸전 위치의 점수에서 큰 것을 더하는 것으로 구할 수 있습니다.

그 다음 두칸 오르는 것은 현재 위치의 점수와 이전 한칸 오르기의 점수를 구하면 됩니다.

마지막에서는 이 중 더 큰 값을 출력하면 됩니다.

하지만 1차원 배열로도 문제를 해결 할 수 있습니다.