BOJ#2096 내려가기

BOJ#2096 내려가기

* 문제

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

* 풀이

메모리 제한이 4MB 입니다.

저는 처음에 재귀 형식으로 풀었다가 바텀업 방식으로 다시 풀었습니다. 

또한, [100001][3] 사이즈의 dp배열과 map 배열을 모두 제거하였습니다.

두가지 형태의 코드 모두 아래에 붙여놓았으니 참고하시면 좋겠습니다.

---

* 나의 코드

https://github.com/stack07142/BOJ/blob/458582301c132e9a61af00c77068edac24669619/BOJ%232096/src/Main.java

<AC 코드>

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

public class Main {

    static int N;

    static final int INF = 100000000;

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

        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        int[] currentLine = new int[3];

        int[] maxScore = new int[3];
        int[] minScore = new int[3];

        Arrays.fill(minScore, INF);

        // Solve
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < 3; i++) currentLine[i] = Integer.parseInt(st.nextToken());

        System.arraycopy(currentLine, 0, maxScore, 0, 3);
        System.arraycopy(currentLine, 0, minScore, 0, 3);

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

            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 3; j++) currentLine[j] = Integer.parseInt(st.nextToken());

            int[] tempMax = {0, 0, 0};
            int[] tempMin = {INF, INF, INF};

            for (int col = 0; col < 3; col++) {

                switch (col) {

                    case 0:
                        for (int j = 0; j < 2; j++) {
                            tempMax[col] = Math.max(tempMax[col], maxScore[j] + currentLine[col]);
                            tempMin[col] = Math.min(tempMin[col], minScore[j] + currentLine[col]);
                        }
                        break;

                    case 1:
                        for (int j = 0; j < 3; j++) {
                            tempMax[col] = Math.max(tempMax[col], maxScore[j] + currentLine[col]);
                            tempMin[col] = Math.min(tempMin[col], minScore[j] + currentLine[col]);
                        }
                        break;

                    case 2:
                        for (int j = 1; j < 3; j++) {
                            tempMax[col] = Math.max(tempMax[col], maxScore[j] + currentLine[col]);
                            tempMin[col] = Math.min(tempMin[col], minScore[j] + currentLine[col]);
                        }
                        break;
                }
            }

            System.arraycopy(tempMax, 0, maxScore, 0, 3);
            System.arraycopy(tempMin, 0, minScore, 0, 3);
        }

        int max = Math.max(maxScore[0], Math.max(maxScore[1], maxScore[2]));
        int min = Math.min(minScore[0], Math.min(minScore[1], minScore[2]));

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

<메모리 초과 코드 - 재귀 형식>

import java.util.Arrays;

/**
 * Created by mymac on 2017. 9. 12..
 */
public class Main2 {

    static int N;
    static int[][] map = new int[100001][3];

    static int[][] dp = new int[100001][3];

    static final int INF = 100000000;

    // Solve Recursive
        /*
        int min = solveMinRecursive(0, 1);
        initDP();
        int max = solveMaxRecursive(0, 1);

        System.out.println(max + " " + min);
        */

    static int solveMinRecursive(int row, int prevCol) {

        if (row == N) return 0;

        if (dp[row][prevCol] != -1) return dp[row][prevCol];

        dp[row][prevCol] = INF;

        for (int col = 0; col < 3; col++) {

            if (Math.abs(col - prevCol) <= 1) {

                dp[row][prevCol] = Math.min(dp[row][prevCol], solveMinRecursive(row + 1, col) + map[row][col]);
            }
        }

        return dp[row][prevCol];
    }

    static int solveMaxRecursive(int row, int prevCol) {

        if (row == N) return 0;

        if (dp[row][prevCol] != -1) return dp[row][prevCol];

        dp[row][prevCol] = 0;

        for (int col = 0; col < 3; col++) {

            if (Math.abs(col - prevCol) <= 1) {

                dp[row][prevCol] = Math.max(dp[row][prevCol], solveMaxRecursive(row + 1, col) + map[row][col]);
            }
        }

        return dp[row][prevCol];
    }

    static void initDP() {

        for (int i = 0; i < 100001; i++) {

            Arrays.fill(dp[i], -1);
        }
    }
}