백준 1932 정수 삼각형 java 풀이

 

문제

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

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

나의 풀이

 DP문제이기 때문에 각 요소의 값을 누적하며 저장한다는 점이 포인트. 이전에 풀어본 Programmers 정수삼각형 문제와 동일하다. 만약 백준에서 이 문제를 먼저 접했다면 힌트가 더 많이 주어지는 샘. 주어지는 삼각형을 이차 배열로 보고 접근하면 생각보다 간단하다. 아래로 내려올수록 값을 누적하도록 하고, 삼각형의 매 요소마다 받을 수 있는 위에 두 수중에 큰값을 선택하도록 하면 되었다. 복습겸 직접 코딩해보았는데 다행이? 금방 작성했다.

 

코드

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

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));
        int num = Integer.parseInt(br.readLine());
        int[][] arr = new int[num][num];
        
        StringTokenizer st;
        for(int i=0; i<num; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<=i; j++) {
                if(i>0&&j==0) {
                    arr[i][0] = Integer.parseInt(st.nextToken()) + arr[i-1][0];
                    continue;
                }
                if(i>0 && j==i) {
                    arr[i][j] = Integer.parseInt(st.nextToken()) + arr[i-1][j-1];
                    continue;
                }
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        for(int i=2; i<num; i++) {
            for(int j=1; j<=i-1; j++) {
                arr[i][j] += Math.max(arr[i-1][j-1], arr[i-1][j]);
            }
        }
        
        int max = 0;
        for(int i=0; i<num; i++) {
            max = Math.max(max, arr[num-1][i]);
        }
        
        bw.write(max+"\n");
        bw.flush();
    }
}