백준 2096번 : 내려가기 java

이 문제는 다이나믹 프로그래밍을 이용하여 푸는 문제입니다.

그런데 이 문제를 보시면 N이 어떤 값이 입력되든지 한 행에는 3개의 값이 들어옵니다.

이렇게 일정한 크기의 부분들에서 반복되는 작업을 할 때 우리는 이것을 더 효율적으로 하기 위해서 슬라이딩 윈도우라는 알고리즘을 사용할 수 있습니다.

슬라이딩 윈도우에 대해서 먼저 설명드리겠습니다.

다음과 같이 위 문제에서 입력값이 들어왔다고 가정해보겠습니다.

이 문제에서 입력값은 한 행의 크기가 3으로 고정되어 있기 때문에 우리는 이것을 한 행씩 처리할 수 있습니다.

1번 행을 처리하고 그 다음 행의 연산을 처리하는 식으로 고정된 크기의 영역을 처리하며 문제를 해결할 수 있습니다.

위 그림의 구간을 먼저 처리한 후 아래 그림의 과정들을 계속 처리합니다.

이 알고리즘을 위 문제에 적용시키는 것을 보여드리도록 하겠습니다.

위의 그림은 예제 1번을 나타낸 그림입니다.

이 문제에서는 다음과 같은 조건으로 값을 더할 수 있다고 합니다.

첫 번째 줄을 입력받을 때는 그 값을 그대로 넣어줍니다.

아래 그림에서 오른쪽에 있는 것들이 max값을 구하기 위한 배열입니다.

이제 다음 행에 들어갈 값을 구해보겠습니다.

빨간색 자리에 들어갈 값은 보라색 구간의 값들 중 가장 큰 값과 파란색 칸의 합입니다.

다음 칸도 구해보겠습니다.

중간에 위치한 칸이므로 위 배열에서 구할 수 있는 범위가 달라졌습니다.

이제 한 줄을 완성했으니 반복문을 통해서 이 과정들을 반복해주면 됩니다.

이렇게 일정 부분들에서 작업을 반복하는 것이 슬라이딩 윈도우입니다.

위의 과정을 반복시켜보겠습니다.

위의 결과에 따라서 이 입력값으로 만들 수 있는 최댓값은 18입니다.

이제 코드를 보여드리겠습니다.

---

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

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

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

            int first = Integer.parseInt(st.nextToken());
            int second = Integer.parseInt(st.nextToken());
            int third = Integer.parseInt(st.nextToken());

            if(i == 0){
                maxArr[0][0] = first;
                maxArr[0][1] = second;
                maxArr[0][2] = third;

                minArr[0][0] = first;
                minArr[0][1] = second;
                minArr[0][2] = third;
                continue;
            }

            maxArr[i][0] = Math.max(maxArr[i-1][0], maxArr[i-1][1]) + first;
            maxArr[i][1] = Math.max(Math.max(maxArr[i-1][0], maxArr[i-1][1]), maxArr[i-1][2]) + second;
            maxArr[i][2] = Math.max(maxArr[i-1][1], maxArr[i-1][2]) + third;

            minArr[i][0] = Math.min(minArr[i-1][0], minArr[i-1][1]) + first;
            minArr[i][1] = Math.min(Math.min(minArr[i-1][0], minArr[i-1][1]), minArr[i-1][2]) + second;
            minArr[i][2] = Math.min(minArr[i-1][1], minArr[i-1][2]) + third;
        }

        int max = Math.max(Math.max(maxArr[N-1][0], maxArr[N-1][1]), maxArr[N-1][2]);
        int min = Math.min(Math.min(minArr[N-1][0], minArr[N-1][1]), minArr[N-1][2]);

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

제가 위에서 설명드린 방법과 같이 코딩하였습니다.

메모리를 조금 더 아끼기 위해서 아래와 같이 코딩할 수도 있습니다.

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

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[] maxArr = new int[3];
        int[] minArr = new int[3];

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

            int first = Integer.parseInt(st.nextToken());
            int second = Integer.parseInt(st.nextToken());
            int third = Integer.parseInt(st.nextToken());

            if(i == 0){
                maxArr[0] = first;
                maxArr[1] = second;
                maxArr[2] = third;

                minArr[0] = first;
                minArr[1] = second;
                minArr[2] = third;
                continue;
            }

            //최대 점수를 구하는 배열
            int ex0 = maxArr[0], ex1 = maxArr[1], ex2 = maxArr[2];

            maxArr[0] = Math.max(ex0, ex1) + first;
            maxArr[1] = Math.max(Math.max(ex0, ex1), ex2) + second;
            maxArr[2] = Math.max(ex1, ex2) + third;

            //최소 점수를 구하는 배열
            int minEx0 = minArr[0], minEx1 = minArr[1], minEx2 = minArr[2];

            minArr[0] = Math.min(minEx0, minEx1) + first;
            minArr[1] = Math.min(Math.min(minEx0, minEx1), minEx2) + second;
            minArr[2] = Math.min(minEx1, minEx2) + third;
        }

        int max = Math.max(Math.max(maxArr[0], maxArr[1]), maxArr[2]);
        int min = Math.min(Math.min(minArr[0], minArr[1]), minArr[2]);

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