[백준] 2579 : 계단 오르기 - Java

• 백준 문제 URL

---

문제 요약

계단이 n개 있고 각 계단에는 점수(score[i])가 있다.
규칙을 지키면서 마지막 계단 n에 반드시 도착할 때 얻을 수 있는 최대 점수를 구하는 문제다.

• 한 번에 1칸 또는 2칸 이동 가능
• 연속 3칸(3개의 계단)을 모두 밟을 수 없음
• 마지막 계단은 반드시 밟아야 함

---

핵심 아이디어

현재 계단 i에 도착하는 “최대 점수”를 생각하면, 그 직전 이동은 케이스가 제한된다.
특히 “3연속 금지” 때문에 단순히 dp[i] = max(dp[i-1], dp[i-2]) + score[i]가 아니라, 연속으로 밟았는지 여부를 점화식에 반영해야 한다.

이 문제는 결국 i번째 계단에 도달하는 최적해가 i-2, i-3까지의 최적해로만 결정되므로 DP로 누적하면 된다.

---

DP 정의 & 점화식

dp 정의

• dp[i] = i번째 계단을 반드시 밟았을 때, 얻을 수 있는 최대 점수

이 정의를 잡으면 최종 정답은 dp[n]이다(문제 조건이 마지막 계단 필수라서).

초기값

• dp[1] = score[1]
• dp[2] = score[1] + score[2] (n이 2 이상일 때만)

dp[1] = score[1];
if (n >= 2) dp[2] = score[1] + score[2];

점화식 (핵심)

i번째 계단을 밟는 방법은 3연속 금지 때문에 딱 두 경우로 정리된다.

1) i-2에서 2칸 점프해서 i로 오는 경우

• 연속 3칸 문제가 생기지 않음
• 점수: dp[i-2] + score[i]

2) i-3 -> i-1 -> i로 오는 경우

• i-1과 i를 연속으로 밟되, 그 전은 i-3이라서 3연속을 피함
• 점수: dp[i-3] + score[i-1] + score[i]

그래서:

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

---

왜 이 점화식이 3연속을 막나?

• dp[i-2] + score[i]는 중간에 i-1을 밟지 않으므로 연속 3칸이 나올 수 없다.
• dp[i-3] + score[i-1] + score[i]는 i-2를 건너뛰기 때문에 (..., i-2, i-1, i) 형태의 3연속이 원천적으로 불가능하다.

즉, “가능한 이동 케이스”를 2개로 제한해서 규칙을 점화식 자체에 녹여버린 형태다.

---

전체 코드(제출용)

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];
        int[] dp = new int[n + 1];

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

        dp[1] = score[1];
        if (n >= 2) dp[2] = score[1] + score[2];

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

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