[백준] 계단 오르기

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

2579번: 계단 오르기

  최근에 동적 계획법 문제를 접했는데 개인적으로 너무 어렵다고 느꼈다. 다만 계속 삽질하면서 얻은 경험적 지식 중 하나는 특정 동적 계획법 문제들은 뒤에서 앞 방향으로 식을 반대로 생각하면 쉬울 수 있다는 것이다. 현재 문제는 이러한 경우 중 하나로, 도착지 입장에서 점화식을 전개하는 방식으로 식을 작성했다.

---

가능한 경우의 수

 N번째 계단에 도달할 수 있는 경우는 크게 2가지가 존재할 수 있다.

1. N-1번째 계단을 밟는 경우
2. N-2번째 계단을 밟는 경우

 N-1번째 계단을 밟는 경우 N-2번째 계단을 추가로 밟으면 3개의 계단을 연속으로 밟게 되는데, 이는 계단을 밟는 규칙에 어긋난다. 이때 계단은 반드시 1칸 또는 2칸 차이로 밟아야 하므로, N-1번째 계단을 밟는 경우 자동적으로 N-3번째 계단을 밟아야 한다. 

 위처럼 계단을 밟으면 N-3, N-2번째 계단은 3칸 연속 같은 조건에 위배되지 않으므로 동일한 점화식을 사용할 수 있다. 이때 N번째 계단에서의 최대값을 M(N)이라고 하고 N번째 계단이 가진 값을 S(N)이라 하면 점화식은 다음과 같다.

M(N) = S(N) + Max( M(N-2), M(N-3) + S(N-1) )

 추가적으로 처음 시작점을 고려하자. 시작점 위치를 0이라고 둘 때, 시작점을 직접적으로 접근할 수 있는 경우는 시작점으로부터 1칸 또는 2칸 뛰는 경우밖에 없으므로 N = 1, 2인 경우다. 두 경우에 대해 점화식을 생각해보자.

• M(2) = S(2) + Max( M(0), M(-1) + S(1) )
• M(1) = S(1) + Max(M(-1), M(-2) + S(0) )

 실제 계단에 -1, -2번째는 존재하지 않지만, 음수 숫자를 0번 계단, 즉 기본 위치와 동일하다고 취급하면 그림에서 설명한 경우와 동일하게 동작할 수 있다. 좀 더 깊게 생각해보면 2번째 계단은 반드시 1번째 계단을 밟는 것이 더 큰 값을 가지며, M(1)은 더 이상 밟을 계단이 없으므로 굳이 시작 위치를 고려하지 않고 N = 1, 2일때 조건을 종료할 수도 있다.

• M(2) = S(2) + S(1)
• M(1) = S(1)

 나는 그냥 점화식에서 -2 ~ 0 사이 인덱스에 대해 0을 반환하도록 구성했다. 코드는 다음과 같다.

N = int(input())
arr = [0]
arr.extend([int(input()) for _ in range(N)])
cache = {}

def dp(idx):
    if -2 <= idx <= 0:
        return 0
    if idx < 0:
        return -100
    if idx in cache.keys():
        return cache[idx]

    val = arr[idx] + max(dp(idx - 2), dp(idx - 3) + arr[idx - 1])
    cache[idx] = val
    return val

print(dp(N))

 인덱스 계산의 편의성을 위해 계단의 점수를 의미하는 arr의 첫번째 위치에 0을 추가했다. dp 함수를 통해 앞에서 보인 점화식을 전개하며, top-down 방식으로 캐싱을 수행하여 연산 횟수를 줄였다.

---

이 문제도 거의 이틀 정도 시간 날 때마다 고민한 것 같다. 어떻게 보면 점화식만 잘 생각해도 엄청 쉬운 문제였다...

비슷한데 고민할게 더 있던 문제: https://www.acmicpc.net/problem/2156

2156번: 포도주 시식