[백준] 2096번 내려가기 (JAVA)

문제

https://www.acmicpc.net/problem/2096

2096번: 내려가기

 

설명

다음 줄로 내려갈 때에는 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다.

DP만 사용해 문제를 풀면 모든 숫자를 배열로 담고 활용해야 하므로 메모리 제약에 걸린다.

따라서, 슬라이딩 윈도우 알고리즘을 같이 사용하면 dp 배열을 계속해서 초기화하면서 문제를 풀 수 있다.

먼저 처음에 maxDP와 minDP를 첫 줄의 숫자들로 초기화한다.

 

다음 줄부터 들어갈 maxDP 값을 구해보면 아래와 같다.

maxDP[0] = 해당 칸 입력값 + max(maxDp[0], maxDP[1])

maxDP[1] = 해당 칸 입력값 + max(maxDp[0], maxDP[1], maxDP[2])

maxDP[2] = 해당 칸 입력값 + max(maxDp[1], maxDP[2])

 

minDP 값도 마찬가지로 구하면 된다.

minDP[0] = 해당 칸 입력값 + min(minDp[0], minDP[1])

minDP[1] = 해당 칸 입력값 + min(minDp[0], minDP[1], minDP[2])

minDP[2] = 해당 칸 입력값 + min(minDp[1], minDP[2])

 

여기서 바로 배열에 옮기면 나중의 계산에 착오가 생기므로 모든 계산이 끝나고 한번에 옮긴다.

int[] maxDP = new int[3];
int[] minDP = new int[3];
int[] temp = new int[3];

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

    int num1 = Integer.parseInt(st.nextToken());
    int num2 = Integer.parseInt(st.nextToken());
    int num3 = Integer.parseInt(st.nextToken());

    // 초기 값 설정
    if (i == 0) {
        maxDP[0] = num1;
        maxDP[1] = num2;
        maxDP[2] = num3;

        minDP[0] = num1;
        minDP[1] = num2;
        minDP[2] = num3;

        continue;
    }

    // 최댓값 DP 값을 구해서 임시 배열인 temp에 담고 나중에 한번에 옮긴다
    temp[0] = num1 + Math.max(maxDP[0], maxDP[1]);
    temp[1] = num2 + Math.max(maxDP[0], Math.max(maxDP[1], maxDP[2]));
    temp[2] = num3 + Math.max(maxDP[1], maxDP[2]);

    maxDP[0] = temp[0];
    maxDP[1] = temp[1];
    maxDP[2] = temp[2];

    // 최솟값 DP 값을 구해서 임시 배열인 temp에 담고 나중에 한번에 옮긴다
    temp[0] = num1 + Math.min(minDP[0], minDP[1]);
    temp[1] = num2 + Math.min(minDP[0], Math.min(minDP[1], minDP[2]));
    temp[2] = num3 + Math.min(minDP[1], minDP[2]);

    minDP[0] = temp[0];
    minDP[1] = temp[1];
    minDP[2] = temp[2];
}

maxDP 배열의 원소 중 최댓값과 minDP 배열의 원소 중 최솟값을 구해서 출력한다. 

max = Integer.MIN_VALUE;
min = Integer.MAX_VALUE;

for (int i = 0; i < 3; i++) {
    max = Math.max(max, maxDP[i]);
    min = Math.min(min, minDP[i]);
}

System.out.println(max + " " + min);

 

전체 코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    static int N;
    static int[] maxDP, minDP, temp;
    static int max, min;

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

        N = Integer.parseInt(br.readLine());

        maxDP = new int[3];
        minDP = new int[3];
        temp = new int[3];

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

            int num1 = Integer.parseInt(st.nextToken());
            int num2 = Integer.parseInt(st.nextToken());
            int num3 = Integer.parseInt(st.nextToken());

            // 초기 값 설정
            if (i == 0) {
                maxDP[0] = num1;
                maxDP[1] = num2;
                maxDP[2] = num3;

                minDP[0] = num1;
                minDP[1] = num2;
                minDP[2] = num3;

                continue;
            }

            // 최댓값 DP 값을 구해서 임시 배열인 temp에 담고 나중에 한번에 옮긴다
            temp[0] = num1 + Math.max(maxDP[0], maxDP[1]);
            temp[1] = num2 + Math.max(maxDP[0], Math.max(maxDP[1], maxDP[2]));
            temp[2] = num3 + Math.max(maxDP[1], maxDP[2]);

            maxDP[0] = temp[0];
            maxDP[1] = temp[1];
            maxDP[2] = temp[2];

            // 최솟값 DP 값을 구해서 임시 배열인 temp에 담고 나중에 한번에 옮긴다
            temp[0] = num1 + Math.min(minDP[0], minDP[1]);
            temp[1] = num2 + Math.min(minDP[0], Math.min(minDP[1], minDP[2]));
            temp[2] = num3 + Math.min(minDP[1], minDP[2]);

            minDP[0] = temp[0];
            minDP[1] = temp[1];
            minDP[2] = temp[2];
        }

        max = Integer.MIN_VALUE;
        min = Integer.MAX_VALUE;

        for (int i = 0; i < 3; i++) {
            max = Math.max(max, maxDP[i]);
            min = Math.min(min, minDP[i]);
        }

        System.out.println(max + " " + min);
    }
}