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

링크

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

---

문제 설명

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

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

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

---

입력 예제

3
1 2 3
4 5 6
4 9 0

---

출력 예제

18 6

---

풀이

첫째 줄에서 마지막 줄까지 내려가면서 최댓값과 최솟값을 구해야 한다. 처음에는 BFS로 내려가면서 탐색하면 되지 않을까 했으나 줄의 최댓값은 100,000으로 모든 경로를 탐색하려면 시간 복잡도는 $O(3^N)$가 된다. 따라서 현실적으로 불가능한 탐색 횟수이므로 무조건 시간 초과가 발생할 수 밖에 없다.

이 문제는 DP로 해결하는 것이 적합하다. 각 위치에서 선택할 수 있는 최댓값, 최솟값을 메모이제이션 배열에 저장하면서 값을 갱신해나간다.

Top-Down

톱 다운 방식은 재귀로 구현할 수 있다. 이때 메모이제이션 배열의 원소들은 -1로 설정해두어 방문 여부를 판단한다.

maxDp = new int[N][3];
minDp = new int[N][3];
numbers = new int[N][3];
//입력값 및 dp 배열 초기화
for (int i = 0; i < N; i++) {
    numbers[i] = Arrays.stream(br.readLine().split(" "))
            .mapToInt(Integer::parseInt)
            .toArray();
    Arrays.fill(maxDp[i], -1);
    Arrays.fill(minDp[i], -1);
}

톱 다운이기에 마지막 줄을 기준으로 위로 올라가면서 재귀를 호출한다. 이때 이미 방문한 값은 기존의 값을 반환한다.

//최댓값을 구하는 재귀 함수
static int findMax(int N, int index) {
    //첫번째 줄은 입력값 반환
    if (N == 0) {
        return numbers[N][index];
    }
    
    //이미 방문한 경우 기존 값 반환
    if (maxDp[N][index] != -1) {
        return maxDp[N][index];
    }
    
    if (index == 0) {
        maxDp[N][index] = Math.max(findMax(N - 1, 0), findMax(N - 1, 1)) + numbers[N][index];
    } else if (index == 1) {
        int tempMax = Math.max(findMax(N - 1, 0), findMax(N - 1, 1));
        maxDp[N][index] = Math.max(tempMax, findMax(N - 1, 2)) + numbers[N][index];
    } else {
        maxDp[N][index] = Math.max(findMax(N - 1, 1), findMax(N - 1, 2)) + numbers[N][index];
    }
    return maxDp[N][index];
}

전체 코드

//백준
public class Main {

    static int[][] maxDp;
    static int[][] minDp;
    static int[][] numbers;

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        maxDp = new int[N][3];
        minDp = new int[N][3];
        numbers = new int[N][3];
        for (int i = 0; i < N; i++) {
            numbers[i] = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt)
                    .toArray();
            Arrays.fill(maxDp[i], -1);
            Arrays.fill(minDp[i], -1);
        }

        int max = 0;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < 3; i++) {
            max = Math.max(findMax(N - 1, i), max);
            min = Math.min(findMin(N - 1, i), min);
        }

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

    static int findMax(int N, int index) {
        if (N == 0) {
            return numbers[N][index];
        }

        if (maxDp[N][index] != -1) {
            return maxDp[N][index];
        }

        if (index == 0) {
            maxDp[N][index] = Math.max(findMax(N - 1, 0), findMax(N - 1, 1)) + numbers[N][index];
        } else if (index == 1) {
            int tempMax = Math.max(findMax(N - 1, 0), findMax(N - 1, 1));
            maxDp[N][index] = Math.max(tempMax, findMax(N - 1, 2)) + numbers[N][index];
        } else {
            maxDp[N][index] = Math.max(findMax(N - 1, 1), findMax(N - 1, 2)) + numbers[N][index];
        }

        return maxDp[N][index];
    }

    static int findMin(int N, int index) {
        if (N == 0) {
            return numbers[N][index];
        }

        if (minDp[N][index] != -1) {
            return minDp[N][index];
        }

        if (index == 0) {
            minDp[N][index] = Math.min(findMin(N - 1, 0), findMin(N - 1, 1)) + numbers[N][index];
        } else if (index == 1) {
            int tempMin = Math.min(findMin(N - 1, 0), findMin(N - 1, 1));
            minDp[N][index] = Math.min(tempMin, findMin(N - 1, 2)) + numbers[N][index];
        } else {
            minDp[N][index] = Math.min(findMin(N - 1, 1), findMin(N - 1, 2)) + numbers[N][index];
        }

        return minDp[N][index];
    }
}

Bottom-Up

바텀 업 방식은 반복문의 형태로 구현할 수 있다. 첫째 줄부터 마지막 줄까지 순서대로 계산해나간다. 순서대로 올라가면 되므로 방문 여부는 체크할 필요는 없다.

전체 코드

//백준
public class Main {

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        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++) {
            maxDp[i] = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt)
                    .toArray();
            minDp[i] = maxDp[i].clone();
        }

        for (int i = 1; i < N; i++) {
            //maxDp 업데이트
            maxDp[i][0] += Math.max(maxDp[i - 1][0], maxDp[i - 1][1]);
            maxDp[i][1] += Math.max(Math.max(maxDp[i - 1][0], maxDp[i - 1][1]), maxDp[i - 1][2]);
            maxDp[i][2] += Math.max(maxDp[i - 1][1], maxDp[i - 1][2]);

            //minDp 업데이트
            minDp[i][0] += Math.min(minDp[i - 1][0], minDp[i - 1][1]);
            minDp[i][1] += Math.min(Math.min(minDp[i - 1][0], minDp[i - 1][1]), minDp[i - 1][2]);
            minDp[i][2] += Math.min(minDp[i - 1][1], minDp[i - 1][2]);
        }

        //마지막 줄에서 최대값과 최소값 찾기
        int max = Math.max(Math.max(maxDp[N - 1][0], maxDp[N - 1][1]), maxDp[N - 1][2]);
        int min = Math.min(Math.min(minDp[N - 1][0], minDp[N - 1][1]), minDp[N - 1][2]);

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