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

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

1932번: 정수 삼각형

 

문제 분석

삼각형에 숫자가 적혀있다.

위에서부터 좌, 혹은 우로 내려가면서 수를 더한다.

맨 밑에 도달했을 때, 숫자 합 최대는?

 

입력 조건

N(삼각형 크기)

그 밑으로 삼각형 크기게 맞게 숙자 입력됨.

 

풀이 과정

1부터 n까지 올라가면서, 각각의 위치에 대해 최대값을 구하면서 내려감.

 

 

전체 코드

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

public class BJ1932_정수삼각형 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[][] triangle = new int[n+1][n+1];
		
		StringTokenizer st;
		for(int i = 1; i < n+1; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 1; j <= i; j++) {
				int tmp = Integer.parseInt(st.nextToken());
				triangle[i][j] = tmp + Math.max(triangle[i-1][j-1], triangle[i-1][j]);
			}
		}
		
		int max = 0;
		for(int j = 1; j < n+1; j++) {
			max = Math.max(max,  triangle[n][j]);
		}
		System.out.println(max);
	}
}