백준 2579 계단 오르기 Java: 점화식과 초기값

백준 2579번 계단 오르기는 마지막 계단을 반드시 밟되 세 계단을 연속해서 밟을 수 없다는 조건을 점화식으로 옮기는 동적 계획법 문제다. 핵심은 마지막 계단 i에 도착하는 방법을 두 경우로만 나누는 것이다.

dp[i] = score[i] + max(
    dp[i - 2],
    dp[i - 3] + score[i - 1]
)

원문에는 이 점화식을 찾고도 백트래킹으로 구현하려 했다는 학습 기록이 남아 있었다. 점화식을 세웠다면 “이 값이 어떤 상태를 뜻하는가”와 초기값을 먼저 고정해야 구현이 다른 방향으로 흐르지 않는다.

dp 상태를 한 문장으로 정의한다

dp[i]를 다음처럼 정의한다.

규칙을 지키면서 i번째 계단을 반드시 밟았을 때 얻을 수 있는 최대 점수

마지막 계단을 반드시 밟아야 하므로 답은 dp[n]이다. 단순히 “i번째까지의 최대 점수”라고만 쓰면 i번째 계단을 건너뛴 경우가 섞일 수 있다. 상태 정의에 i번째를 밟는다는 조건을 넣는 것이 중요하다.

마지막 이동은 두 경우뿐이다

i번째 계단에 도착하는 직전 상황을 나눠 보자.

i-2에서 두 칸 올라온 경우

i-1을 밟지 않았으므로 i-2까지의 최적해에 현재 점수를 더할 수 있다.

dp[i - 2] + score[i]

i-1에서 한 칸 올라온 경우

i-1과 i를 연속으로 밟았다. 세 계단 연속을 피하려면 i-2는 밟을 수 없으므로 그 앞은 i-3이어야 한다.

dp[i - 3] + score[i - 1] + score[i]

두 값 가운데 큰 값을 고르면 점화식이 된다.

dp[i] = max(
    dp[i - 2] + score[i],
    dp[i - 3] + score[i - 1] + score[i]
)

두 식의 공통 항인 score[i]를 밖으로 빼면 처음의 형태와 같다.

초기값은 작은 입력을 직접 적어 정한다

점화식은 i-3을 참조하므로 작은 입력을 별도로 확인한다.

dp[0] = 0
dp[1] = score[1]
dp[2] = score[1] + score[2]

계단이 3개라면 세 개를 모두 밟을 수 없다.

dp[3] = score[3] + max(score[1], score[2])

일반 점화식에 i=3을 넣어도 dp[0]=0 덕분에 같은 결과가 나온다.

dp[3] = score[3] + max(dp[1], dp[0] + score[2])

Java bottom-up 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] score = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            score[i] = Integer.parseInt(br.readLine());
        }

        if (n == 1) {
            System.out.println(score[1]);
            return;
        }

        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = score[1];
        dp[2] = score[1] + score[2];

        for (int i = 3; i <= n; i++) {
            dp[i] = score[i] + Math.max(
                dp[i - 2],
                dp[i - 3] + score[i - 1]
            );
        }

        System.out.println(dp[n]);
    }
}

반복문은 각 계단을 한 번씩 처리한다.

• 시간 복잡도: O(n)
• 공간 복잡도: O(n)

공식 제한에서 계단 수는 최대 300개이고 계단 점수는 최대 10,000이므로 모든 점수를 더한 상한도 3,000,000이다. Java int 범위 안에 들어간다.

왜 그리디로 고르기 어려운가

현재 보이는 두 계단 중 점수가 큰 쪽을 고르는 방식은 이후의 연속 세 계단 제한을 고려하지 못한다. 지금 i-1을 선택하면 다음 선택에서 i-2를 밟았는지까지 영향을 받는다. 지역적으로 큰 점수가 전체 경로의 최대 점수를 보장하지 않는다.

반면 DP는 dp[i-2]와 dp[i-3]에 앞부분의 최적 결과를 저장한다. 마지막 선택만 두 경우로 분리하면 앞의 경로를 다시 전부 탐색할 필요가 없다.

top-down 풀이에서 확인할 부분

원문의 재귀 메모이제이션도 같은 점화식을 사용하므로 방향은 맞다. 다만 다음 항목을 명확히 해야 한다.

• n <= 0의 반환값을 0으로 둘 것
• 계산하지 않은 상태와 실제 점수 0을 구분할 sentinel을 정할 것
• 재귀 호출 전에 dp[n]을 확인할 것
• 입력 크기가 커질 때 호출 스택 한계를 검토할 것

이 문제의 입력 크기에서는 top-down도 가능하지만, bottom-up은 초기값과 계산 순서가 드러나 디버깅하기 쉽다.

오답을 줄이는 체크리스트

1. dp[i]가 i번째 계단을 반드시 밟는 상태인지 확인한다.
2. i-1과 i를 밟을 때 i-2가 제외되는지 본다.
3. n=1, n=2, n=3을 손으로 계산한다.
4. 마지막 답을 배열 최댓값이 아니라 dp[n]으로 출력한다.
5. 점화식을 찾은 뒤 다른 탐색 방식으로 구현하고 있지 않은지 점검한다.

참고 자료

• 백준 온라인 저지 2579번: 계단 오르기