[ Baekjoon ] 1932번 - 정수 삼각형

1932번: 정수 삼각형

 

풀이 방법

왼쪽 위의 대각선과 오른쪽 위의 대각선에 존재하는 값을 비교해 큰 값을 더해주는 방식으로 위에서 아래로 가는 방법을 선택했다. 마지막 배열에 존재하는 값들 중에서 가장 큰 값이 최대가 되는 경로에 있는 수의 합이된다.

 

구현 코드

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

public class Q_1932 {
	static int n;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		n = Integer.parseInt(br.readLine());
		int[][] array = new int[n][n];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j <= i; j++) {
				array[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		dp(array);
		
		int result = 0;
		for (int i = 0; i < n; i++) {
			result = Math.max(result, array[n-1][i]);
		}
		
		System.out.println(result);
	}
	
	static void dp(int[][] dp) {
		for (int i = 1; i < n; i++) {
			for (int j = 0; j <= i; j++) {
				if (j-1 >= 0)
					dp[i][j] = dp[i][j] + Math.max(dp[i-1][j-1], dp[i-1][j]);
				else
					dp[i][j] = dp[i][j] + dp[i-1][j];
				
			}
		}
	}
}