[Java][1932] 정수 삼각형

문제:

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

1932번: 정수 삼각형

코드:

import java.util.*;

public class Main {
    public static int n;
    // 값 저장용
    public static int [][] arr = new int[505][505];
    public static int [][] dp = new int[505][505];
    public static void run(){
        for(int i=2;i<n;i++){
            for(int j=1;j<i;j++){
                dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-1]) + arr[i][j];
            }
        }

    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

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

        // 초깃값
        dp[0][0] = arr[0][0];
        for(int i=1;i<n;i++){
            dp[i][0] = dp[i-1][0]+arr[i][0];
        }

        for(int i=1;i<n;i++){
            dp[i][i] = dp[i-1][i-1]+arr[i][i];
        }

        run();

        int maxval = Integer.MIN_VALUE;
        for(int i=0;i<n;i++){
            maxval = Math.max(maxval,dp[n-1][i]);
        }
        System.out.println(maxval);

    }
}

 

7 
3 8 
8 1 0 
2 7 4 4 
4 5 2 6 5 

형태로 arr 2차원 배열에 저장함
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

점화식
dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-1]) + arr[i][j];

dp[i][j] 의 값은 dp[i-1][j](바로 위) , dp[i-1][j-1] (대각선 왼쪽 위)의 값 중
최대값 + arr[i][j] 이다.

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

초기값 설정

맨 왼쪽 혹은 맨 오른쪽 값의 경우 위 범위 문제로 위 점화식을 정의할 수 없으므로
따로 저장한다.

        dp[0][0] = arr[0][0];
        for(int i=1;i<n;i++){
            dp[i][0] = dp[i-1][0]+arr[i][0];
        }

        for(int i=1;i<n;i++){
            dp[i][i] = dp[i-1][i-1]+arr[i][i];
        }
        
맨 왼쪽은 자신의 바로 위의 값만 맨 오른쪽은 자신의 대각선 왼쪽 위 값만
가져 올 수 있으므로 그 값들만 더하도록 한다.

이후 점화식을 적용해 (run()) 모든 배열을 채우고 dp 맨 아랫줄 값 중 가장 큰 값을 출력한다.

 

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

디버깅 포함 코드

import java.util.*;

public class Main {
    public static int n;
    public static int [][] arr = new int[505][505];
    public static int [][] dp = new int[505][505];
    public static void run(){
        for(int i=2;i<n;i++){
            for(int j=1;j<i;j++){
                dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-1]) + arr[i][j];
            }
        }

    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

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

        /*
        // 디버깅
        for(int i=0;i<n;i++){
            for(int j=0;j<i+1;j++){
                System.out.print(arr[i][j]+" ");
            }
            System.out.println();
        }

         */

        // 초깃값
        dp[0][0] = arr[0][0];
        for(int i=1;i<n;i++){
            dp[i][0] = dp[i-1][0]+arr[i][0];
        }

        for(int i=1;i<n;i++){
            dp[i][i] = dp[i-1][i-1]+arr[i][i];
        }

        /*
        // 디버깅
        for(int i=0;i<n;i++){
            for(int j=0;j<i+1;j++){
                System.out.print(dp[i][j]+" ");
            }
            System.out.println();
        }

         */

        run();

        /*
        for(int i=0;i<n;i++){
            for(int j=0;j<i+1;j++){
                System.out.print(dp[i][j]+" ");
            }
            System.out.println();
        }

         */

        int maxval = Integer.MIN_VALUE;
        for(int i=0;i<n;i++){
            maxval = Math.max(maxval,dp[n-1][i]);
        }
        System.out.println(maxval);

    }
}