[다이나믹 프로그래밍] 백준 2579번: 계단 오르기 / 실버 3

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

2579번: 계단 오르기

잘 알려진 계단 오르기 문제와 유사하지만, 까다로운 조건 하나가 추가 되었다.

바로 연속한 세 계단을 오를 수는 없다는 것이다. 

이걸 어떻게 dp에 적용할 수 있을지 고민하는 것 때문에 실버3인데도 꽤 어려움을 느꼈다.

 

어떤 x번째 계단에 도착하는 상황을 가정해보자.

이전 스텝에서는 x-1번째 또는 x-2번째 계단에 있었을 것이다. 

그럼 그 전 스텝에서는? 이렇게 전전 스텝까지 생각해봤을 때, x번째 계단을 도착하는 경우는 다음과 같다.

 

우선 x-2, x-1, x  --> 이 경우는 연속한 세 계단을 밟은 경우이므로 불가능한 경우다.

 

1.   x-3, x-1, x ( 이 경우는 2칸 오르고, 1칸 올라서 x에 도달한 경우)

2.   x-3, x-2, x ( 이 경우는 1칸 오르고, 2칸 올라서 x에 도달한 경우)

3.   x-4, x-2, x ( 이 경우는 2칸 오르고, 2칸 올라서 x에 도달한 경우)

즉, 전전스텝까지 생각해봤을 때 3가지 경우가 가능하다. 나는 여기서 힌트를 얻었다. 

 

처음엔 아 그럼 dp를 3*n 배열로 만들어야 되나 생각했지만, 

직전에 몇칸 올라서 x에 도달했는가만 다음 스텝에 영향을 주기때문에 2*n배열로 dp를 구성하기로 했다.

이 원리에 따라 작성한 코드는 다음과 같다.

import sys
input = sys.stdin.readline
n = int(input())
lst = []
for _ in range(n):
    lst.append(int(input()))

if n == 1:
    print(lst[0])
else:
    # [elem1, elem2] => 1전 칸에서 올라왔을 때의 맥스, 2전 칸에서 올라왔을 떄의 맥스
    dp = [[0 for _ in range(2)] for _ in range(n)]
    dp[0] = [lst[0], lst[0]]
    dp[1] = [dp[0][0] + lst[1], lst[1]]
    for i in range(2, n):
        dp[i][0] = dp[i-1][1] + lst[i]
        dp[i][1] = max(dp[i-2]) + lst[i]
    print(max(dp[-1]))

<16>

dp[i][0] = dp[i-1][1] + lst[i]

: 2칸오르고 1칸 올라서 i번째에 도달한 경우이다. 전전 스텝에서 2칸올랐기 때문에 dp[i-1] 중에서 1번째 값을 가져와야 한다.

 

<17>

dp[i][1] = max(dp[i-2]) + lst[i]

: 직전에 2칸 올라서 i번째에 도달한 경우이다. 전전 스텝에서 2칸올랐을 수도, 1칸올랐을 수도 있기 때문에 이 중에 큰값을 취하도록 한다.