[백준 1932번] 정수 삼각형 - JAVA

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

1932번: 정수 삼각형

풀이

사용한 알고리즘 : DP

 

풀이전략

arr[i][j]는 i행 i열에 입력된 값을 의미한다.

d[i][j]는 i행 i열에서 가질 수 있는 1행에서부터 덧셈된 합의 최대값을 의미한다.

 

먼저 삼각형의 크기를 나타내는 n의 범위가 1<=n<=500 이라고 했으므로

int arr[][] = new int[n+1][n+1]

int d[][] = new int[n+1][n+1] 로 선언한다.

 

d[i][j]는 바로 윗줄의 대각선 왼쪽, 오른쪽에 있는 최대값에서 현재 값을 더한 것 중 큰 수를 저장하므로

d[i][j] = Math.max(d[i-1][j-1]+arr[i][j], d[i-1][j]+arr[i][j]); 라는 식을 통해 i행 j열에서의 최대 총합값을 구한다.

 

그 후 맨 마지막 행에서의 값들 (  d[n][1] ~ d[n][n]  )  중 가장 큰 값을 출력하면 정답을 구할 수 있다.

 

아래 그림은 이해를 위해 첨부한다.

 

제출코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());

        int arr[][] = new int[n+1][n+1];
        int d[][] = new int[n+1][n+1];

        for(int i=1;i<n+1;++i){
            st = new StringTokenizer(br.readLine());
            int k=1;
            while(st.hasMoreTokens()){
                arr[i][k]=Integer.parseInt(st.nextToken());
                ++k;
            }
        }

        for(int i=1;i<n+1;++i){
            for(int j=1;j<n+1;++j){
                d[i][j]=Math.max(d[i-1][j-1]+arr[i][j],
                        d[i-1][j]+arr[i][j]);
            }
        }

        int maxVal=d[n][1];
        for(int i=2;i<n+1;++i){
            maxVal=Math.max(d[n][i],maxVal);
        }

        bw.write(maxVal+"\n");
        bw.flush();
        bw.close();
    }
}