Baekjoon 1932 정수 삼각형 JAVA

1932번: 정수 삼각형

문제

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

출력

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

풀이

소스는 3부분으로 나누어져 있다.

1. 입력부

2. 누적 합을 생성하는 부분

3. 최대 값을 찾는 부분이다.

 

누적 합을 생성하는 부분을 예제 입력의 값으로 보면 이해가 쉬워진다.

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

4행의 '7'을 거치는 경로는 3행의 '8' 또는 3행의 '1'값을 지나 올 수 밖에 없다. 

5행의 '2'의 경우는 4행의 '7' 또는 4행의 왼쪽에 위치한 '4'이다.

이것을 좌표값으로 본다면 [i][j]를 거치기 위해서는 [i-1][j-1] 혹은 [i-1][j]를 거친다.

이 값들을 위에서부터 순차적으로 실행하면서 그 순간순간에 Math.Max를 만족하는 값을 다음 값으로 만들면 된다.

코드

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

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int [][] arr = new int[n][n];

		for(int i=0;i<n;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0;j<=i;j++)
				arr[i][j]=Integer.parseInt(st.nextToken());
		}
		
		for(int i=1;i<n;i++)
		{
			arr[i][0]+=arr[i-1][0];
			for(int j=1;j<=i;j++)
			arr[i][j]+=Math.max(arr[i-1][j-1],arr[i-1][j]);
		}

		int max=0;
		for(int i=0;i<n;i++)
			max=Math.max(max, arr[n-1][i]);
		
		System.out.println(max);
	}
}