[DP] 2578번 계단 오르기

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

알고리즘

• Dynamic Programming

풀이

포인트

• bottom-up 구현
• 세 계단을 연속적으로 오르지 못하는 제한 조건을 활용하여 점화식 변형

Dynamic Programming

전형적인 dp 문제로, i번째 계단을 방문했을 때, 그 상태를 기반으로 i+1번째 계단, i+2번재 계단을 방문할 때의 점수 상태를 업데이트하면 된다. 이때, 연속적으로 3개의 계단을 방문하면 안되므로, i번째 계단 방문 상태가 이미 연속 두 계단을 방문한 상태라면 i+1번째 계단은 방문 못하고 i+2번째 계단만 방문할 수 있다. 만약, 연속 두 계단이 아닌, 연속 하나의 계단만 방문한 상태라면 i+1,i+2 계단 모두 방문할 수 있다.

우선 2차원 dp 테이블을 아래와 같이 정의한다.

• $dp[i][j]$: 현재 j개의 연속적인 계단을 방문한 상태에서 i번째 계단을 방문했을 때의 점수 최댓값
  • $j == 1$ 이라면, 현재 1개의 연속적인 계단을 방문한 상태이므로 1칸 또는 2칸을 뛸 수 있다.
  • $j == 2$ 이라면, 현재 2개의 연속적인 계단을 방문한 상태이므로 2칸만 뛸 수 있다.

$dp[i][j]$를 방문한 상태에서, 점화식은 j값에 따라서 아래와 같의 정의한다.

• $j == 1$ 이라면,
  • 한 칸 이동하기: $dp[i+1][2] = max(dp[i+1][2], dp[i][j] + a[i+1])$
  • 두 칸 이동하기: $dp[i+2][1] = max(dp[i+2][1], dp[i][j] + a[i+2])$
• $j == 2$ 이라면,
  • 두 칸 이동하기: $dp[i+2][1] = max(dp[i+2][1], dp[i][j] + a[i+2])$

물론, index 조건에 유의하여 프로그래밍해야한다.

[Source Code]

n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))
if n == 1:
    print(a[0])
    exit()
dp = [[-1]*4 for _ in range(n)]
# dp 테이블 초기값 설정.
dp[0][1] = a[0]
dp[1][1] = a[1]
for i in range(n):
    for j in [1,2]:
        if dp[i][j] == -1:
            continue
        if j == 1:
            # 한칸 이동하기.
            if i+1 < n:
                dp[i+1][2] = max(dp[i+1][2], dp[i][j] + a[i+1])
            # 두칸 이동하기.
            if i+2 < n:
                dp[i+2][1] = max(dp[i+2][1], dp[i][j] + a[i+2])
        elif j == 2:
            # 두칸 이동하기.
            if i+2 < n:
                dp[i+2][1] = max(dp[i+2][1], dp[i][j] + a[i+2])
print(max(dp[n-1]))