[백준 자바 2096] 내려가기 (골드5)

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

 

설명

N은 1 이상 10만 이하로, 한 줄에는 3칸이 있고 각 칸에는 최대 9까지 올 수 있으므로, 최악의 경우의 합을 더해도 9 * 10만 = 90만으로 int의 최댓값보다 작다. 

 

또한 메모리가 4MB인데, 4byte(int) * 3칸 * 10만 줄 = 1.2MB로, 입력받는 배열에 최댓값, 최솟값 + 기타 연산하면서 생기는 객체들까지 고려하면 메모리 초과가 날 것 같았다. 

 

그래서 입력 배열은 따로 만들지 않고 최댓값 배열과 최솟값 배열만 만들되, 각각 2 * 3 배열을 만들어서 값을 재사용하기로 했다. 

우선 N과 최댓값 배열 maxArr, 최솟값 배열 minArr을 선언해준다. 그리고 각 배열을 2*3으로 초기화해준다. 

 

i / j	0	1	2
0	0	0	0
1	0	0	0

(블로그 스킨이 표를 이상하게 표현해서.. 양해 부탁드려요)

각 배열은 초기값이 이렇게 되어 있을 거다. 

이제부터 0행은 기존값을, 1행은 기존값으로부터 최댓값을 계산한 후, 다 계산하면 이를 다시 0행으로 옮겨줄 거다. 

 

우선 최댓값을 구하는 부분부터.

먼저 3칸의 입력을 받아서 x0, x1, x2에 넣어주었다. (최솟값 배열 계산할 때도 쓰여야 해서)

 

다음은 1행에 대해서 0행 중 최댓값을 가져온 뒤, 입력값을 각각 열에 맞게 더해준다. 

 

i / j	0	1	2
0	0	0	0
1	1	2	3

첫 번째 예제인 N=3, 그 다음 첫 줄인 1 2 3을 받을 때, 33번째 줄까지 처리하면 위와 같게 된다. (0행이 시작이라 0으로 초기화되어 있으므로 입력값만 받게 된다.)

 

i / j	0	1	2
0	1	2	3
1	1	2	3

그다음 1행의 계산이 끝나면 이를 다시 0행으로 옮겨준다. 

 

i / j	0	1	2
0	1	2	3
1	2 + 4 = 6	3 + 5 = 9	3 + 6 = 9

그리고 그 다음 입력인 4 5 6이 입력될 때 33번째 줄까지 처리되면 위와 같고, 

 

i / j	0	1	2
0	6	9	9
1	2 + 4 = 6	3 + 5 = 9	3 + 6 = 9

이를 다시 0행으로 옮기면 위와 같다. 

 

i / j	0	1	2
0	6	9	9
1	9 + 4 = 13	9 + 9 = 18	9 + 0 = 9

마지막으로 입력이 4 9 0이 입력된 후 33번째 줄까지 처리하면 위와 같고,

 

i / j	0	1	2
0	13	18	9
1	13	18	9

이를 0행으로 옮기면 최종적으로 위와 같다.

 

 

계산이 다 끝나면 마지막의 0행으로 옮기는 로직에 의해 0행의 값들 중 최댓값을 구하면 된다. 

최솟값도 최댓값 계산한 방식으로 똑같이 하면 돼서 넣진 않았다. 

 

끝!

---

전체 코드

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

public class Main {

    static int N;
    static int[][] maxArr;
    static int[][] minArr;

    static int stoi(String s) {
        return Integer.parseInt(s);
    }

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

        N = stoi(st.nextToken());

        maxArr = new int[2][3];
        minArr = new int[2][3];

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

            int x0 = stoi(st.nextToken());
            int x1 = stoi(st.nextToken());
            int x2 = stoi(st.nextToken());

            maxArr[1][0] = Math.max(maxArr[0][0], maxArr[0][1]) + x0;
            maxArr[1][1] = Math.max(maxArr[0][0], Math.max(maxArr[0][1], maxArr[0][2])) + x1;
            maxArr[1][2] = Math.max(maxArr[0][1], maxArr[0][2]) + x2;

            maxArr[0][0] = maxArr[1][0];
            maxArr[0][1] = maxArr[1][1];
            maxArr[0][2] = maxArr[1][2];

            minArr[1][0] = Math.min(minArr[0][0], minArr[0][1]) + x0;
            minArr[1][1] = Math.min(minArr[0][0], Math.min(minArr[0][1], minArr[0][2])) + x1;
            minArr[1][2] = Math.min(minArr[0][1], minArr[0][2]) + x2;

            minArr[0][0] = minArr[1][0];
            minArr[0][1] = minArr[1][1];
            minArr[0][2] = minArr[1][2];
        }

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

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