[Java]백준 BaekJoon.AC 2096 : 내려가기 (다이나믹 프로그래밍)

 

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

2096번: 내려가기

 

 

문자 하나 잘못 입력해서 삽 좀 펐다...

입력 리스트 크기를 num[N][N]으로 설정해서, 메모리를 아무리 줄여도 메모리 초과가 발생했다ㅋㅋㅋㅋ;;

분명 num[N][3]으로 작성했던거 같은데...^^

 

 

 

max와 min을 따로 분리해 값을 구했다.

각 리스트(maxS, minS)에 그 칸에 해당하는 가장 큰 값 또는 가장 작은 값을 저장하는 방식이다.

 

 

입력 리스트를 한 칸씩 방문하며

그 칸이 왼쪽에 있다면 오른쪽과 아래 값을 갱신해주고,

가운데에 있다면 왼아오 값을 갱신해주고,

오른쪽에 있다면 왼아 값을 갱신해줬다.

 

 

 

<메모 참고>

 

 

 

 

<기본적인 코드>

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

public class Main {
    static int[][] num;
    static int[][] maxS;
    static int[][] minS;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        num = new int[N][3];
        maxS = new int[N][3];
        minS = new int[N][3];

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

        for(int i=0; i<3; i++){ //첫줄 값 미리 작성
            maxS[0][i] = num[0][i];
            minS[0][i] = num[0][i];
        }

        for(int i=0; i<N-1; i++){ //마지막줄은 해당시키지 않음
            for(int j=0; j<3; j++){
                calX(i, j);
                calN(i, j);
            }
        }

        System.out.print(Math.max(Math.max(maxS[N-1][0], maxS[N-1][1]), maxS[N-1][2]) + " ");
        System.out.print(Math.min(Math.min(minS[N-1][0], minS[N-1][1]), minS[N-1][2]));
    }

    public static void calX(int i, int j){
        if(j==0 || j==1){
            maxS[i+1][0] = Math.max(maxS[i][j]+num[i+1][0], maxS[i+1][0]);
        }

        maxS[i+1][1] = Math.max(maxS[i][j]+num[i+1][1], maxS[i+1][1]);

        if(j==1 || j==2) {
            maxS[i+1][2] = Math.max(maxS[i][j] + num[i+1][2], maxS[i+1][2]);
        }
    }

    public static void calN(int i, int j){
        if(j==0 || j==1){
            if(minS[i+1][0] == 0){
                minS[i+1][0] = minS[i][j]+num[i+1][0];
            }else {
                minS[i+1][0] = Math.min(minS[i][j]+num[i+1][0], minS[i+1][0]);
            }
        }

        if(minS[i+1][1] == 0){
            minS[i+1][1] = minS[i][j]+num[i+1][1];
        }else {
            minS[i+1][1] = Math.min(minS[i][j]+num[i+1][1], minS[i+1][1]);
        }

        if(j==1 || j==2){
            if(minS[i+1][2] == 0){
                minS[i+1][2] = minS[i][j]+num[i+1][2];
            }else {
                minS[i+1][2] = Math.min(minS[i][j]+num[i+1][2], minS[i+1][2]);
            }
        }
    }
}

 

 

 

 

처음엔 이 코드도 메모리 초과가 발생해서(num[N][N]으로 크기를 설정했으니... 그것도 모르고)

메모리를 줄이도록 노력했다. 문제의 메모리 조건도 애초에 타이트하게 뽑아둔 것 같길래... 내가 잘못한 줄 알았다.

 

 

 

그래서 나온 코드가 아래 코드인데, 아래 코드는 maxS와 minS 리스트의 크기를 [2][3]으로 설정했다.

굳이 N줄이 아니더라도 이전에 계산한 리스트는 더이상 필요하지 않고, 아직 계산하지 않은 값도 굳이 가지고 있을 필요가 없기 때문이다.

 

새로 계산해 갱신된 max 줄과 min 줄(maxS[0][1], minS[0][1])이 완성되면 위로 옮겨주고 다시 0으로 맞춰주는 방식.

 

 

 

 

<maxS와 minS 크기를 조절해준 코드. 메모리 단축>

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

public class Main {
    static int[][] num;
    static int[][] maxS;
    static int[][] minS;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        num = new int[N][3];
        maxS = new int[2][3];
        minS = new int[2][3];

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

        for(int k=0; k<3; k++){ //첫줄 값 미리 작성
            maxS[0][k] = num[0][k];
            minS[0][k] = num[0][k];
        }

        for(int i=0; i<N-1; i++){ //마지막줄은 해당시키지 않음
            for(int j=0; j<3; j++){
                calX(i, j);
                calN(i, j);
            }

            for(int k=0; k<3; k++){ //새로 입력된 값 0번째줄로 끌어올리기
                maxS[0][k] = maxS[1][k];
                maxS[1][k] = 0;
                minS[0][k] = minS[1][k];
                minS[1][k] = 0;
            }
        }

        System.out.print(Math.max(Math.max(maxS[0][0], maxS[0][1]), maxS[0][2]) + " ");
        System.out.print(Math.min(Math.min(minS[0][0], minS[0][1]), minS[0][2]));
    }

    public static void calX(int i, int j){
        if(j==0 || j==1){
            maxS[1][0] = Math.max(maxS[0][j]+num[i+1][0], maxS[1][0]);
        }

        maxS[1][1] = Math.max(maxS[0][j]+num[i+1][1], maxS[1][1]);

        if(j==1 || j==2) {
            maxS[1][2] = Math.max(maxS[0][j] + num[i+1][2], maxS[1][2]);
        }
    }

    public static void calN(int i, int j){
        if(j==0 || j==1){
            if(minS[1][0] == 0){
                minS[1][0] = minS[0][j]+num[i+1][0];
            }else {
                minS[1][0] = Math.min(minS[0][j]+num[i+1][0], minS[1][0]);
            }
        }

        if(minS[1][1] == 0){
            minS[1][1] = minS[0][j]+num[i+1][1];
        }else {
            minS[1][1] = Math.min(minS[0][j]+num[i+1][1], minS[1][1]);
        }

        if(j==1 || j==2){
            if(minS[1][2] == 0){
                minS[1][2] = minS[0][j]+num[i+1][2];
            }else {
                minS[1][2] = Math.min(minS[0][j]+num[i+1][2], minS[1][2]);
            }
        }
    }
}

 

 

 

근데 이 코드도 메모리 초과가 발생한 것이다.(num[N][N]으로 크기를 설정했으니까....ㅜㅜ)

그래서 입력 받는 리스트 num은 아예 일차원 리스트로 줄이려 했다.

이미 계산이 끝난 입력 리스트는 더이상 필요하지 않고, 아직 입력받지 않은 빈 리스트를 미리 만들어 가지고 있을 필요가 없으니.

 

 

그래서 num의 크기도 조절해주려는 순간, num의 크기가 [N][N]인 걸 발견했다...

앗... 아차하며 아까 틀렸던 코드의 num리스트 크기를 조절해주니, 아주 손쉽게 통과가 되더라.

 

 

아래 리스트도 num 크기를 바꿔주니 당연히 통과 되었고.

아마 num리스트 크기를 줄였다면 그것 또한 당연히 통과 됐겠지 뭐... 

 

 

 

분명히 삽질이었던건 맞지만...

 

다이나믹 프로그래밍에서 N줄 크기의 리스트가 필요하지 않단 생각을 해보게 되서 의미있는 삽질이었던 것 같다.

 

굳이 모든 칸의 리스트를 그대로 끌고 갈 필요가 없음을 알게 됐다. 좋은 삽질이었다......