[백준] 2096. 내려가기 (DP/Java)

[백준] 2096. 내려가기

📌 풀이 과정

• 3개의 열과 N개의 행으로 이루어진 숫자판이 주어진다.
• 맨 윗줄에서 시작하여 맨 아랫줄로 내려오면서 합계의 최댓값과 최솟값을 구해야 한다.
• 단, 한 칸 아래로 이동할 때, 같은 열 또는 인접한 열로만 이동 가능하다.

처음에는 각 열에서 이동 가능한 경우의 수를 모두 고려한

완전 탐색으로 코드를 작성했지만.. 시간 초과가 떴다...

완전 탐색으로 풀면 3^N의 연산을 해야 하며, 이는 시간 제한(1초) 내에 처리할 수 없는 연산량이었다.

따라서, DP를 사용해야 한다!!!! 🥹디피.. 싫어....

 

❤️‍🔥 점화식

최댓값과 최솟값을 각각 계산해야 하기 때문에 두 개의 DP 배열을 사용했다.

maxD[x][y]: x행, y열까지 내려왔을 때 얻을 수 있는 최대 합
minD[x][y]: x행, y열까지 내려왔을 때 얻을 수 있는 최소 합

각 행의 모든 열에 대해 가능한 이전 위치들을 고려해서 계산하면 된다.

현재 위치 (x, y)로 올 수 있는 이전 위치는 (x-1, y-1), (x-1, y), (x-1, y+1)이며

범위 내에 존재하는 값만 처리해주면 된다.

 

✨ 제출 코드 - 2차원 배열

메모리: 54980 KB

시간: 428 ms

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

public class Main {

    static int N, M = 3;
    static int[][] map;
    static int[] dy = {-1, 0, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][M];

        int[][] minD = new int[N][M];
        int[][] maxD = new int[N][M];
        for(int i = 0; i < N; i++){
            Arrays.fill(minD[i], Integer.MAX_VALUE);
            Arrays.fill(maxD[i], Integer.MIN_VALUE);
        }

        for(int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0; j < M; j++){
                map[i][j] = Integer.parseInt(st.nextToken());

                if(i == 0){
                    minD[i][j] = map[i][j];
                    maxD[i][j] = map[i][j];
                }
            }
        }

        for(int x = 1; x < N; x++){
            for(int y = 0; y < M; y++){
                for(int i = 0; i < 3; i++){
                    int ny = y + dy[i];
                    if(ny < 0 || ny >= M) continue;

                    minD[x][y] = Math.min(minD[x][y], minD[x-1][ny] + map[x][y]);
                    maxD[x][y] = Math.max(maxD[x][y], maxD[x-1][ny] + map[x][y]);
                }
            }
        }

        System.out.println(Math.max(Math.max(maxD[N-1][0], maxD[N-1][1]), maxD[N-1][2])
            + " " + Math.min(Math.min(minD[N-1][0], minD[N-1][1]), minD[N-1][2]));
    }

}

 

✨ 제출 코드 - 1차원 배열

메모리: 51584 KB

시간: 364 ms

각 행에서는 이전 행의 정보만 필요하다.

이전 행의 값을 저장하고, 현재 행의 값을 계산하면서 덮어쓰면 메모리 사용량을 줄일 수 있다.

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

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[][] map = new int[N][3];

        // 각 열의 최소/최대값을 저장할 배열
        int[] min = new int[3];
        int[] max = new int[3];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < 3; i++){
            min[i] = max[i] = Integer.parseInt(st.nextToken());
        }

        for(int i = 1; i < N; i++){
            st = new StringTokenizer(br.readLine());

            // 새로운 최대, 최소값을 저장할 임시 배열
            int[] new_max = new int[3];
            int[] new_min = new int[3];

            // [0]열 처리
            int num = Integer.parseInt(st.nextToken());
            int tmp_max = Math.max(max[0], max[1]);
            int tmp_min = Math.min(min[0], min[1]);
            new_max[0] = tmp_max + num;
            new_min[0] = tmp_min + num;

            // [1]열 처리
            num = Integer.parseInt(st.nextToken());
            tmp_max = Math.max(Math.max(max[0], max[1]), max[2]);
            tmp_min = Math.min(Math.min(min[0], min[1]), min[2]);
            new_max[1] = tmp_max + num;
            new_min[1] = tmp_min + num;

            // [2]열 처리
            num = Integer.parseInt(st.nextToken());
            tmp_max = Math.max(max[1], max[2]);
            tmp_min = Math.min(min[1], min[2]);
            new_max[2] = tmp_max + num;
            new_min[2] = tmp_min + num;

            // 다음 행 계산을 위해 배열 업데이트
            max = new_max;
            min = new_min;
        }

        System.out.println(Math.max(Math.max(max[0], max[1]), max[2])
            + " " + Math.min(Math.min(min[0], min[1]), min[2]));
    }
}