내려가기 (백준 2096) 문제 풀이

🔗 문제 링크

---

📝 문제 설명

내려가기 문제는 세 개의 숫자가 있는 N개의 줄이 주어질 때,
위에서 아래로 내려오면서 인접한(혹은 바로 옆) 숫자들 중 하나를 선택해
최대 합과 최소 합을 구하는 문제임.
즉, 한 줄에서 선택한 숫자의 인접한 번호(같은 열 또는 바로 옆 열)로만 이동할 수 있음.

---

✅ 풀이 접근 방식

문제를 풀기 위해 동적 계획법(DP)을 사용함.
각 행에서 선택한 열에 따라 최대 합과 최소 합을 동시에 관리할 수 있도록
3차원 DP 배열을 사용함.

• DP 배열 정의:

  • dp[i][j][0]: i번째 줄에서 j번째 열을 선택했을 때,
    위쪽 줄부터 현재까지의 최대 합
  • dp[i][j][1]: i번째 줄에서 j번째 열을 선택했을 때,
    위쪽 줄부터 현재까지의 최소 합

• 초기값:
  첫 번째 줄의 각 열에 대해서는,
  dp[0][j][0] = dp[0][j][1] = map[0][j]로 초기화함.

• 점화식 (전이):
  i번째 줄에서 j번째 열을 선택하면,
  이전 줄의 j, j-1, j+1 열 중에서 전이할 수 있음.
  각 경우에 대해 합을 구하고,
  최대 합은 최댓값, 최소 합은 최솟값으로 갱신함.

  예를 들어, j가 0(첫 번째 열)인 경우에는
  이전 줄의 0번 열과 1번 열에서만 전이할 수 있음.

---

🔍 코드 분석

아래 코드는 위의 아이디어를 구현한 예시임.

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

public class Main {
    private static StringTokenizer st;
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
    private static int N;
    
    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        int[][] map = new int[N][3];
        // 입력 받기
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 3; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        // dp[i][j][0]: 최대합, dp[i][j][1]: 최소합
        int[][][] dp = new int[N][3][2];
        // 첫 줄 초기화
        dp[0][0][0] = dp[0][0][1] = map[0][0];
        dp[0][1][0] = dp[0][1][1] = map[0][1];
        dp[0][2][0] = dp[0][2][1] = map[0][2];
        
        int[] answer = {0, Integer.MAX_VALUE};
        // 2번째 줄부터 전이하며 dp 배열 갱신
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < 3; j++) {
                dp[i][j][0] = 0;
                dp[i][j][1] = Integer.MAX_VALUE;
                if (j == 0) {  // 첫 번째 열은 인접한 열: 0, 1
                    dp[i][j][0] = Math.max(dp[i][j][0], dp[i - 1][0][0] + map[i][j]);
                    dp[i][j][0] = Math.max(dp[i][j][0], dp[i - 1][1][0] + map[i][j]);
                    dp[i][j][1] = Math.min(dp[i][j][1], dp[i - 1][0][1] + map[i][j]);
                    dp[i][j][1] = Math.min(dp[i][j][1], dp[i - 1][1][1] + map[i][j]);
                } else if (j == 1) {  // 두 번째 열은 인접한 열: 0, 1, 2
                    dp[i][j][0] = Math.max(dp[i][j][0], dp[i - 1][0][0] + map[i][j]);
                    dp[i][j][0] = Math.max(dp[i][j][0], dp[i - 1][1][0] + map[i][j]);
                    dp[i][j][0] = Math.max(dp[i][j][0], dp[i - 1][2][0] + map[i][j]);
                    dp[i][j][1] = Math.min(dp[i][j][1], dp[i - 1][0][1] + map[i][j]);
                    dp[i][j][1] = Math.min(dp[i][j][1], dp[i - 1][1][1] + map[i][j]);
                    dp[i][j][1] = Math.min(dp[i][j][1], dp[i - 1][2][1] + map[i][j]);
                } else {  // 세 번째 열은 인접한 열: 1, 2
                    dp[i][j][0] = Math.max(dp[i][j][0], dp[i - 1][1][0] + map[i][j]);
                    dp[i][j][0] = Math.max(dp[i][j][0], dp[i - 1][2][0] + map[i][j]);
                    dp[i][j][1] = Math.min(dp[i][j][1], dp[i - 1][1][1] + map[i][j]);
                    dp[i][j][1] = Math.min(dp[i][j][1], dp[i - 1][2][1] + map[i][j]);
                }
            }
        }
        // 마지막 줄에서 최대합과 최소합을 찾음
        for (int i = 0; i < 3; i++) {
            answer[0] = Math.max(answer[0], dp[N - 1][i][0]);
            answer[1] = Math.min(answer[1], dp[N - 1][i][1]);
        }
        System.out.println(answer[0] + " " + answer[1]);
    }
}

---

💡 결론

• 동적 계획법을 이용한 접근:
  각 행에서 선택할 수 있는 세 가지 경우를 고려하며,
  이전 행에서 가능한 값들을 전이하여 최대 합과 최소 합을 동시에 계산함.
• 점화식 구현:
  • 첫 번째 열: 이전 행의 0번, 1번 열에서 전이
  • 두 번째 열: 이전 행의 0번, 1번, 2번 열에서 전이
  • 세 번째 열: 이전 행의 1번, 2번 열에서 전이
• 최종 답안:
  마지막 행에서 최대값과 최소값을 각각 구하고, 이를 출력함.

이와 같이 문제에서 주어진 제약 조건에 맞춰 DP를 구성하면,
빠르고 효율적으로 문제를 해결할 수 있음.