문제 탐색하기

입력 자료 정리

1. 입력값 n은 이후 들어올 입력 줄의 개수이다
2. 각 줄마다 3개의 입력값이 들어오며, 각 인덱스의 원소를 의미한다
3. 이 원소는 최댓값과 최솟값을 구하는데 사용될 비용이다

해결방법 추론

1. 이전 RGB 문제처럼 각 줄마다 3칸으로 고정되어 있기 때문에,
   DP를 활용하여 이전 값을 누적해나가고, 마지막 n-1번째 줄의 3개의 값을 모두 비교하여
   최댓값과 최솟값을 구하면 될 것이다 라고 생각하였다
2. 문제에서 주어진 그림을 이해하면,
   인덱스 범위 내에서 내 바로 이전 인덱스를 누적하면 된다는 것을 알 수 있다
3. 대각선 범위까지 모두 포함해야 하며,
   양 끝 인덱스의 경우에는 인덱스 범위만 벗어나지 않게 생각하면 된다
4. 이 문제에서 한가지 주의깊게 봐야할 것이 있는데, 바로 메모리 제한이다
5. 따라서 배열을 제한적으로 사용해야하므로, 공간복잡도를 잘 계산하여 문제를 해결해야 한다
6. 이 문제에서는 두가지 방법으로 풀었다.
   하나는 3차원 배열을 이용하는 것이고,
   다른 하나는 2차원 배열 두가지를 이용하는 것이다
7. 3차원 배열의 크기는 n x 3 x 2이고, 2차원 배열의 크기는 n x 3이다.

공간 복잡도 계산

1. 두 배열의 크기는 사실 같다 n x 3 x 2나, n x 3배열 2개나 계산해보면 같다는 것을 알 수 있다
2. 따라서 두 배열 방법 중 하나를 선택해서 풀면 되며,
   이때 공간복잡도를 계산하여 메모리 초과가 발생하는지 체크하기만 하면 된다
3. n은 10만이 최대이므로 100,000 x 3 x 2가 최대 크기가 될 것이며,
   int형 배열이므로 4byte를 곱해주면 된다
4. 이때 전체 크기는 2,400,000byte이며 다시 바꾸면 2.4MB가 된다.
5. 메모리 제한은 4MB이고, 자바의 경우 JVM을 생각하여 256MB이므로
   두 방법 모두 문제없이 해결할 수 있다!

점화식 설계

1. 이제 점화식을 설계해보자. 3차원 배열을 기준으로 설계하였다
2. int형 3차원 배열을 n x 3 x 2 크기로 선언한다
3. n x 3은 배열의 각 원소의 누적합이 저장될 것이고 마지막 2의 크기를 갖는 배열은
   0번 인덱스는 max값, 1번 인덱스는 min값을 갖도록 설계하였다
4. 최댓값과 최솟값을 구하는 점화식의 차이는 Math.max를 사용하냐 Math.min을 사용하냐 차이이다
5. 각 0번, 1번 2번 인덱스에 대해 점화식을 나타내면 다음과 같다

최댓값 점화식 설계

• dp[i][0][0] = Math.max(dp[i-1][0][0], dp[i-1][1][0]) + dp[i][0][0];
• dp[i][1][0] = Math.max(dp[i-1][0][0], Math.max(dp[i-1][1][0], dp[i-1][2][0])) + dp[i][1][0];
• dp[i][2][0] = dp[i][2][0] = Math.max(dp[i-1][1][0],dp[i-1][2][0]) + dp[i][2][0];

최솟값 점화식 설계

• dp[i][0][1] = Math.min(dp[i-1][0][1], dp[i-1][1][1]) + dp[i][0][1];
• dp[i][1][1] = Math.min(dp[i-1][0][1], Math.min(dp[i-1][1][1], dp[i-1][2][1])) + dp[i][1][1];
• dp[i][2][1] = Math.min(dp[i-1][1][1], dp[i-1][2][1]) + dp[i][2][1];

6. dp의 n-1번째에 누적된 최댓값과 최솟값이 있을 것이므로,
   각각 n-1번째 인덱스의 3인덱스에서 최댓값과 최솟값을 가려내어 출력한다면 원하는 결과를
   얻을 수 있다

시간 복잡도 계산

1. 시간복잡도는 어떻게 될까?
2. DP덕분에 아주 효율적으로 처리할 수 있다
3. 바로 n만큼만 순회하면 된다. 이전 값을 1번인덱스부터 n까지 순회하므로
   시간복잡도는 O(n)이 된다
4. 따라서 시간제한 걱정없이 문제를 해결할 수 있다

코드 설계하기

입력 자료 정리

1. 앞서 살펴봤듯이 입력값은 int형 3차원 배열의 dp의 각 인덱스에 넣어준다
2. 크기는 n x 3 x 2이며, 이중포문을 통해 각 줄의 입력값들을 넣어준다
3. 0번 인덱스와 1번 인덱스의 값을 같은 값으로 넣어주기 위해,
   별도의 변수로 먼저 받은 다음 해당 원시타입의 변수를 배열에 넣어주며도록 설계하였다

점화식 코드 설계

1. 위에서 설계한 점화식을 그대로 1부터 n만큼 돌면서 누적하도록 설계하면 된다
2. 처음 풀이에서는 최댓값과 최솟값을 다르게 구분하여 했는데,
   더 효율적으로 한다면 하나의 포문에서 모두를 구할 수 있기에 변경하여 다시 제출하였다
3. 하나의 포문에 6개의 점화식이 들어가도록 설계하였다

출력값 설계

1. 이후 출력값은 n-1번째 인덱스의 0번 인덱스값들과 1번 인덱스값들을 비교하여 출력하면된다
2. 최댓값을 먼저 출력하고 최솟값을 이어서 출력하면 정답이 된다.

정답 코드

(1회차 시도 성공!)
[3차원 배열 DP 풀이]

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


/**
 * 풀이 과정:
 * - 고민과 풀이:
 *
 * - 문제 해결:
 *
 * 시간복잡도: O()
 * 공간복잡도: O()
 *
 */


public class Main {

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

        int n = Integer.parseInt(br.readLine());
        int[][][] dp = new int[n][3][2];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 3; j++) {
                int a = Integer.parseInt(st.nextToken());
                dp[i][j][0] = a;
                dp[i][j][1] = a;
            }
        }

        for (int i = 1; i < n; i++) {
            dp[i][0][0] = Math.max(dp[i-1][0][0], dp[i-1][1][0]) + dp[i][0][0];
            dp[i][1][0] = Math.max(dp[i-1][0][0], Math.max(dp[i-1][1][0], dp[i-1][2][0])) + dp[i][1][0];
            dp[i][2][0] = Math.max(dp[i-1][1][0], dp[i-1][2][0]) + dp[i][2][0];
            
            dp[i][0][1] = Math.min(dp[i-1][0][1], dp[i-1][1][1]) + dp[i][0][1];
            dp[i][1][1] = Math.min(dp[i-1][0][1], Math.min(dp[i-1][1][1], dp[i-1][2][1])) + dp[i][1][1];
            dp[i][2][1] = Math.min(dp[i-1][1][1], dp[i-1][2][1]) + dp[i][2][1];
        }
        bw.write(Math.max(Math.max(dp[n-1][0][0], dp[n-1][1][0]), dp[n-1][2][0])+" "
                + Math.min(Math.min(dp[n-1][0][1], dp[n-1][1][1]), dp[n-1][2][1]));

        br.close();
        bw.close();
    }
}

[2차원 배열 DP 2개 활용 풀이]

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[][] maxDp = new int[n][3];
        int[][] minDp = new int[n][3];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 3; j++) {
                int a = Integer.parseInt(st.nextToken());
                maxDp[i][j] = a;
                minDp[i][j] = a;
            }
        }

        for (int i = 1; i < n; i++) {

            maxDp[i][0] = Math.max(maxDp[i-1][0], maxDp[i-1][1]) + maxDp[i][0];
            maxDp[i][1] = Math.max(maxDp[i-1][0], Math.max(maxDp[i-1][1], maxDp[i-1][2])) + maxDp[i][1];
            maxDp[i][2] = Math.max(maxDp[i-1][1], maxDp[i-1][2]) + maxDp[i][2];

            minDp[i][0] = Math.min(minDp[i-1][0], minDp[i-1][1]) + minDp[i][0];
            minDp[i][1] = Math.min(minDp[i-1][0], Math.min(minDp[i-1][1], minDp[i-1][2])) + minDp[i][1];
            minDp[i][2] = Math.min(minDp[i-1][1], minDp[i-1][2]) + minDp[i][2];

        }
        bw.write(Math.max(Math.max(maxDp[n-1][0], maxDp[n-1][1]), maxDp[n-1][2])+" " 
        + Math.min(Math.min(minDp[n-1][0], minDp[n-1][1]), minDp[n-1][2]));


        br.close();
        bw.close();
    }
}

문제 링크

2096번 - 내려가기