[자바] 백준 1932번: 정수 삼각형

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

1932번: 정수 삼각형

 

삼각형의 맨 꼭대기에서부터 출발해서,

가질 수 있는 최댓값을 각 자리마다 계산해주면 된다.

한 행 안에서 맨 왼쪽 요소는, 그 윗칸의 맨 왼쪽 요소로부터 올 수밖에 없고

한 행 안에서 맨 오른쪽 요소도 마찬가지로, 그 윗칸의 맨 오른쪽 요소로부터 올 수 밖에 없다.

그렇다면 나머지 중간 요소들은?

윗칸의 한 칸 왼쪽 요소, 윗칸의 현재 위치 요소 중 더 큰값으로부터 오면 최댓값을 만들 수 있다.

이렇게 최댓값을 자리별로 모두 구해놓은 다음,

마지막 행에서 최댓값을 찾아 출력하면 된다.

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

public class P1932 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());

		int[][] triangle = new int[n][n];
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j <= i; j++) {
				triangle[i][j] = Integer.parseInt(st.nextToken());

			}
		}

		int[][] sum = new int[n][n];

		sum[0][0] = triangle[0][0];
		for (int i = 1; i < n; i++) {
			sum[i][0] = sum[i - 1][0] + triangle[i][0];
			sum[i][i] = sum[i - 1][i - 1] + triangle[i][i];
			for (int j = 1; j < i; j++) {
				sum[i][j] = (sum[i - 1][j - 1] > sum[i - 1][j] ? sum[i - 1][j - 1] : sum[i - 1][j]) + triangle[i][j];
			}
		}

		int result = 0;
		for (int i = 0; i < n; i++) {
			if (sum[n - 1][i] > result)
				result = sum[n - 1][i];
		}

		System.out.println(result);

	}

}