[백준/Java] 2578 - 계단 오르기

2578 - 계단 오르기

문제 바로가기

1. 문제 요구사항

• 입력: 계단의 개수와 각 계단의 점수가 주어진다.
• 조건:
  1. 계단은 한 번에 1칸 또는 2칸씩 오를 수 있다.
  2. 연속된 3개의 계단을 모두 밟으면 안 된다. (가장 까다로운 조건)
  3. 마지막 도착 계단은 반드시 밟아야 한다.
• 출력: 얻을 수 있는 총 점수의 최댓값.

2. 접근 방식 (Algorithm)

문제를 풀기 위해 마지막 $N$번째 계단에 도착하는 경우의 수를 따져보았다.
조건 2(3연속 불가) 때문에 $N$에 도착하는 방법은 딱 두 가지뿐이다.

경우의 수 1: 2칸 점프해서 도착 ($N-2 \rightarrow N$)

• 전전 계단($N-2$)에서 껑충 뛰어온 경우다.
• 이 경우 연속 3칸 조건에 걸릴 일이 없으므로 안심하고 더하면 된다.
• 식: dp[n-2] + arr[n]

경우의 수 2: 1칸 걸어서 도착 ($N-1 \rightarrow N$)

• 바로 전 계단($N-1$)에서 올라온 경우다.
• 주의: 여기서 dp[n-1]을 그대로 더해버리면 안 된다. 만약 $N-1$ 계단도 $N-2$에서 1칸 올라온 거라면, $N-2 \rightarrow N-1 \rightarrow N$이 되어 3연속 밟기 위반이 된다.
• 따라서, $N-1$을 밟고 $N$으로 오려면, $N-1$ 이전에는 무조건 $N-3$에서 점프해서 왔어야 한다.
• 식: dp[n-3] + arr[n-1] + arr[n]

최종 점화식

위 두 경우 중 더 큰 값을 선택하면 된다.
$dp[n] = arr[n] + \max(dp[n-2], arr[n-1] + dp[n-3])$

3. 코드

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

public class Main {

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

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int[] arr = new int[n+1];
        int[] dp = new int[n+1];

        for(int i=1; i<=n; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i] = Integer.parseInt(st.nextToken());
        }

        dp[1] = arr[1];

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

        dp[2] = dp[1] + arr[2];

        if(n <= 2) {
            System.out.println(dp[n]);
            return;
        }
        for(int i=3; i<=n; i++) {
            int cost = arr[i];

            dp[i] = cost + Math.max(dp[i-2], arr[i-1] + dp[i-3]);
        }
        System.out.println(dp[n]);
    }
}

4. 느낀점 & 배운점

1. DP는 거꾸로 생각하자

• 처음부터 올라가는 시뮬레이션을 하려니 머리가 복잡했다. 도착점을 기준으로 "직전에 어디서 왔을까?"를 나누니 점화식이 보였다.

2. 조건이 까다로울수록 이전(Previous)을 더 멀리 봐야 한다

• '연속 3칸 불가' 조건 때문에 n-1뿐만 아니라 n-3까지 봐야 한다는 점이 어려웠다. DP에서는 '현재 상태를 정의하기 위해 필요한 과거의 상태'가 무엇인지 파악하는 게 핵심인 것 같다.

3. 인덱스 에러 처리 (IndexOutOfBound)

• 처음에는 배열 크기를 딱 N+1로 잡았더니, $N=1$일 때 dp[2]를 참조하다 에러가 났다.
• 조건문(if)으로 막을 수도 있지만, 문제의 최댓값(300)만큼 배열을 미리 잡아두면 조건문 없이 깔끔하게 해결된다는 팁을 배웠다.