내려가기

문제

2096번: 내려가기

문제 설명

N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.

먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.

별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.

제한 사항

첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. 첫째 줄에 얻을 수 있는 최대 점수와 최소 점수를 띄어서 출력한다.

입출력 예

입력	출력
3
1 2 3
4 5 6
4 9 0	18 6
3
0 0 0
0 0 0
0 0 0	0 0

아이디어

dp (min, max 따로 설정)

제출 코드

// 메모리 제한 오류
import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;

public class five2096 {
    public int n;
    public int[][] board;
    public int[][] maxDp;
    public int[][] minDp;
    public int max = Integer.MIN_VALUE;
    public int min = Integer.MAX_VALUE;

    public void solution() throws IOException {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        board = new int[n][n];
        maxDp = new int[n][n];
        minDp = new int[n][n];

        for (int i = 0; i < n; i++) {
            Arrays.fill(minDp[i], Integer.MAX_VALUE);
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = sc.nextInt();
            }
        }

        for (int i = 0; i < n; i++) {
            maxDp[0][i] = board[0][i];
            minDp[0][i] = board[0][i];
        }

        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n; j++) {
                int current = maxDp[i][j];
                maxDp[i + 1][j] = Math.max(maxDp[i + 1][j], current + board[i + 1][j]);

                if (j == 0) {
                    maxDp[i + 1][j + 1] = Math.max(maxDp[i + 1][j + 1], current + board[i + 1][j + 1]);
                } else if (j == n - 1) {
                    maxDp[i + 1][j - 1] = Math.max(maxDp[i + 1][j - 1], current + board[i + 1][j - 1]);
                } else {
                    maxDp[i + 1][j + 1] = Math.max(maxDp[i + 1][j + 1], current + board[i + 1][j + 1]);
                    maxDp[i + 1][j - 1] = Math.max(maxDp[i + 1][j - 1], current + board[i + 1][j - 1]);
                }

                current = minDp[i][j];
                minDp[i + 1][j] = Math.min(minDp[i + 1][j], current + board[i + 1][j]);

                if (j == 0) {
                    minDp[i + 1][j + 1] = Math.min(minDp[i + 1][j + 1], current + board[i + 1][j + 1]);
                } else if (j == n - 1) {
                    minDp[i + 1][j - 1] = Math.min(minDp[i + 1][j - 1], current + board[i + 1][j - 1]);
                } else {
                    minDp[i + 1][j + 1] = Math.min(minDp[i + 1][j + 1], current + board[i + 1][j + 1]);
                    minDp[i + 1][j - 1] = Math.min(minDp[i + 1][j - 1], current + board[i + 1][j - 1]);
                }
            }
        }

        int maxValue = Integer.MIN_VALUE;
        int minValue = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            maxValue = Math.max(maxValue, maxDp[n - 1][i]);
            minValue = Math.min(minValue, minDp[n - 1][i]);
        }

        System.out.printf("%d %d", maxValue, minValue);
    }

    public static void main(String[] args) throws IOException {
        new five2096().solution();
    }
}

모범 풀이

import java.io.IOException;
import java.util.Scanner;

public class five2096 {
    public int n;
    public int[][] board;
    public int[] maxDp;
    public int[] minDp;

    public void solution() throws IOException {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        board = new int[n][3];
        maxDp = new int[3];
        minDp = new int[3];

        for (int i = 0; i < n; i++) {
            int x1 = sc.nextInt();
            int x2 = sc.nextInt();
            int x3 = sc.nextInt();

            if (i == 0) {
                maxDp[0] = minDp[0] = x1;
                maxDp[1] = minDp[1] = x2;
                maxDp[2] = minDp[2] = x3;
            } else {
                int beforeX1 = maxDp[0];
                int beforeX2 = maxDp[2];
                maxDp[0] = Math.max(maxDp[0], maxDp[1]) + x1;
                maxDp[2] = Math.max(maxDp[2], maxDp[1]) + x3;
                maxDp[1] = Math.max(Math.max(beforeX1, maxDp[1]), beforeX2) + x2;

                beforeX1 = minDp[0];
                beforeX2 = minDp[2];
                minDp[0] = Math.min(minDp[0], minDp[1]) + x1;
                minDp[2] = Math.min(minDp[2], minDp[1]) + x3;
                minDp[1] = Math.min(Math.min(beforeX1, minDp[1]), beforeX2) + x2;
            }
        }
        System.out.printf("%d %d",
                Math.max(Math.max(maxDp[0], maxDp[1]), maxDp[2]),
                Math.min(Math.min(minDp[0], minDp[1]), minDp[2]));

    }

    public static void main(String[] args) throws IOException {
        new five2096().solution();
    }
}