[백준] 1932번 정수 삼각형 _ JAVA ( 주석 설명 )

1번

- 배열을 계산하는데 ArrayIndexOut이 안되려고 1열에 '0'을 넣은 N*(N+1) 배열을 만드려다가 시간이 오래 걸린 문제..

(결국 그냥 간단히 index 체크 구문 써서 해결했다..)

 

→ 0행을 복사하고, Math.max(dp[i-1][j-1], dp[i-1][j]) 로 접근했다.

(마지막 N-1행에서 max 값을 찾기 위한 검사가 필요하다)

 

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

public class Main {
    static int[][] ary; //n개의 수열을 입력받을 공간
    static Integer[][] dp; //범위가 0부터 시작하므로, 빈 공간을 체크하기 위해 Integer 배열을 사용해야 한다.

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

        int N = Integer.parseInt(br.readLine()); //삼각형의 크기를 입력받는다.
        ary = new int[N][N]; //정수 삼각형을 저장하기 위한 배열을 생성한다.
        dp = new Integer[N][N]; //dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-1]) 를 위한 공간을 생성한다.

        for(int i=0;i<N;++i){
            StringTokenizer st = new StringTokenizer(br.readLine());

            int j = 0;
            while(st.hasMoreTokens()){
                ary[i][j] = Integer.parseInt(st.nextToken()); //각 입력을 2차원 배열에 넣는다.
                ++j;
            }
        }

        for(int i=0;i<ary.length;++i){ //0행은 그대로 복사한다.
            dp[0][i] = ary[0][i];
        }

        solve(N-1,N-1); //최대값을 구하기 위해 배열 전체 범위를 (N-1) * (N-1) 계산한다.

        int max = -1; //입력 최소값이 0이다.
        for(int i=0;i<N;++i){ //N-1행의 0열부터 N-1열까지 중 가장 큰 값이 최대가 되는 경로에 있는 수의 합이다.
            max = Math.max(max, dp[N-1][i]);
        }

        System.out.println(max); //합이 최대가 되는 경로에 있는 수의 합을 출력한다.
    }

    //Top-down 방식
    private static Integer solve(int row, int column) {
        if(row<0 || column<0) //배열 범위를 벗어난 경우 계산값에 영향을 주지 않기 위해 0을 리턴한다.
            return 0;

        if(dp[row][column]==null){ //dp[][] 배열이 null, 처음 계산할 경우
            for(int i=1;i<=row;++i){
                for(int j=0;j<=column;++j){
                    dp[i][j] = Math.max(solve(i-1,j), solve(i-1,j-1))+ary[i][j]; //바로 위에 있는 값과, 위의 옆에 있는 값 중 큰 값을 더한다.
                }
            }
        }

        return dp[row][column];
    }
}

 

---

 

2번

→ N-1행을 복사하고, Math.max(dp[i+1][j], dp[i+1][j+1])으로 dp[0][0] 에 최댓값을 저장하는 방식이다.

(1번과 비교해 max 값을 찾기 위한 검사가 필요하지 않다.)

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

public class Main {
    static int[][] ary; //n개의 수열을 입력받을 공간
    static Integer[][] dp; //범위가 0부터 시작하므로, 빈 공간을 체크하기 위해 Integer 배열을 사용해야 한다.

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

        int N = Integer.parseInt(br.readLine()); //삼각형의 크기를 입력받는다.
        ary = new int[N][N]; //정수 삼각형을 저장하기 위한 배열을 생성한다.
        dp = new Integer[N][N]; //dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-1]) 를 위한 공간을 생성한다.

        for(int i=0;i<N;++i){
            StringTokenizer st = new StringTokenizer(br.readLine());

            int j = 0;
            while(st.hasMoreTokens()){
                ary[i][j] = Integer.parseInt(st.nextToken()); //각 입력을 2차원 배열에 넣는다.
                ++j;
            }
        }

        for(int i=0;i<ary.length;++i){ //N-1, 제일 아래 행은 그대로 복사한다.
            dp[N-1][i] = ary[N-1][i];
        }

        System.out.println(solve2(0,0));//(0,0) 값을 최대값으로 만든다. //합이 최대가 되는 경로에 있는 수의 합을 출력한다.
    }

    private static int solve2(int row, int column){
        if(row == ary.length-1)  //마지막(N-1) 행일 경우 dp 값 리턴 반환
            return dp[row][column];

        if(dp[row][column]==null){ //바로 아래행과 아래행의 오른쪽 열과 비교해서 큰 값을 더한다.
            dp[row][column] = Math.max(solve2(row+1,column),solve2(row+1,column+1))+ary[row][column];
        }
        
        return dp[row][column]; //경로 상의 최대값으로 만든 dp[0][0]을 리턴한다.
    }
}