[백준] 2096 : 내려가기 - Java

• 백준 문제 URL

---

문제 요약

n줄짜리 3열 숫자 배열이 주어질 때, 맨 위에서 맨 아래까지 내려가며 얻을 수 있는 최대 점수와 최소 점수를 각각 구해서 "최대 최소" 형태로 출력하는 문제다.
이동은 자기 바로 아래 또는 양 옆 아래 3방향으로만 가능하다.

---

핵심 아이디어

각 열의 점수는 “이전 줄의 인접한 2~3개 열들”에서만 오므로, 줄 단위로 최적값을 누적하면 된다.
또, 최대/최소가 동시에 필요하니 maxDP와 minDP를 따로 관리하면서 이전 줄 → 현재 줄로 갱신한다.

이 문제의 특징은 메모리 제한(4MB)이 빡세서 전체 dp[n][3]을 저장하기보다는 이전 줄 1줄만 유지(rolling DP)하는 방식이 표준이다.

---

DP 정의 & 점화식

dp 정의

• prevMax[0/1/2] = 이전 줄의 1/2/3번째 열에서 내려와서 얻은 최대 점수
• prevMin[0/1/2] = 이전 줄의 1/2/3번째 열에서 내려와서 얻은 최소 점수

초기값(첫 줄)

첫 줄은 더 올라갈 곳이 없으므로 그대로 시작:

prevMax[0] = prevMin[0] = 첫줄첫칸;
prevMax[1] = prevMin[1] = 첫줄둘째칸;
prevMax[2] = prevMin[2] = 첫줄셋째칸;

점화식(3열 각각)

현재 줄의 a, b, c에 대해:

• 1열(a): 위의 1열/2열 중 최대/최소 선택
  curMax[0] = max(prevMax[0], prevMax[1]) + a
curMin[0] = min(prevMin[0], prevMin[1]) + a

• 2열(b): 위의 1/2/3열 중 최대/최소 선택
  curMax[1] = max(prevMax[0], max(prevMax[1], prevMax[2])) + b
curMin[1] = min(prevMin[0], min(prevMin[1], prevMin[2])) + b

• 3열(c): 위의 2열/3열 중 최대/최소 선택
  curMax[2] = max(prevMax[1], prevMax[2]) + c
curMin[2] = min(prevMin[1], prevMin[2]) + c

---

Rolling DP(메모리 최적화)

이 문제는 n이 최대 100,000이라서 전체 dp[n][3]을 만들면 메모리 초과 위험이 있다.
그래서 이전 줄(prev) → 현재 줄(cur) → prev에 다시 할당하는 방식으로 1줄만 유지한다.

prevMax = curMax;
prevMin = curMin;

---

전체 코드(제출용)

package A5DP.Baekjoon;

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

public class G2096내려가기 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        // 이전 줄의 최대/최소 DP
        int[] prevMax = new int[3];
        int[] prevMin = new int[3];

        // 첫 줄 입력
        StringTokenizer st = new StringTokenizer(br.readLine());
        prevMax[0] = prevMin[0] = Integer.parseInt(st.nextToken());
        prevMax[1] = prevMin[1] = Integer.parseInt(st.nextToken());
        prevMax[2] = prevMin[2] = Integer.parseInt(st.nextToken());

        // 2번째 줄부터 갱신
        for (int i = 1; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            int[] curMax = new int[3];
            int[] curMin = new int[3];

            // max 갱신
            curMax[0] = Math.max(prevMax[0], prevMax[1]) + a;
            curMax[1] = Math.max(prevMax[0], Math.max(prevMax[1], prevMax[2])) + b;
            curMax[2] = Math.max(prevMax[1], prevMax[2]) + c;

            // min 갱신
            curMin[0] = Math.min(prevMin[0], prevMin[1]) + a;
            curMin[1] = Math.min(prevMin[0], Math.min(prevMin[1], prevMin[2])) + b;
            curMin[2] = Math.min(prevMin[1], prevMin[2]) + c;

            // 다음 줄을 위해 갱신
            prevMax = curMax;
            prevMin = curMin;
        }

        int maxScore = Math.max(prevMax[0], Math.max(prevMax[1], prevMax[2]));
        int minScore = Math.min(prevMin[0], Math.min(prevMin[1], prevMin[2]));

        System.out.println(maxScore + " " + minScore);
    }
}