[백준/Silver I] 정수 삼각형 - 1932

[Silver I] 정수 삼각형 - 1932

문제 링크

성능 요약

메모리: 33988 KB, 시간: 404 ms

분류

다이나믹 프로그래밍

제출 일자

2024년 11월 21일 01:13:47

문제 설명

        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번째 줄까지 정수 삼각형이 주어진다.

출력

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

 

제출 코드

// https://www.acmicpc.net/problem/1932
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()); // 삼각형의 크기
        // 정수 삼각형 입력받기
        ArrayList<Integer>[] tri = new ArrayList[n];
        StringTokenizer st;
        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            tri[i] = new ArrayList<>();
            while(st.hasMoreTokens()) {
                tri[i].add(Integer.parseInt(st.nextToken()));
            }
        }

        int temp1, temp2;
        // 가장 윗 줄부터 합 계산해 나가기
        for(int i=1; i<n; i++) {
            tri[i].set(0, tri[i - 1].get(0) + tri[i].get(0)); // 가장 왼쪽 끝의 값은 항상 전 줄 왼쪽 끝 값을 더한거
            // 양 끝을 제외하고는 전 줄의 왼쪽, 오른쪽 값을 더한 값 중 큰 값을 저장
            for (int j = 1; j < i; j++) {
                temp1 = tri[i].get(j) + tri[i - 1].get(j - 1);
                temp2 = tri[i].get(j) + tri[i - 1].get(j);
                tri[i].set(j, Math.max(temp1, temp2));
            }
            tri[i].set(i, tri[i - 1].get(i - 1) + tri[i].get(i)); // 가장 오른쪽 끝의 값은 항상 전 줄 오른쪽 끝 값을 더한거
        }
        tri[n-1].stream().max(Integer::compareTo).ifPresent(System.out::println); // 가장 마지막 줄의 max값 구하기
    }
}