[JAVA] 백준 1932번 - 정수 삼각형

 

📖 문제

 

📋 코드

import java.util.*;
public class Main {
	
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int DP[][] = new int[n][n];
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= i; j++) {
				int x = sc.nextInt();
				if(i == 0) DP[i][j] = x;
				else {
					if(j == 0) {
						DP[i][j] = x + DP[i-1][j];
					}else {
						DP[i][j] = x + Math.max(DP[i-1][j-1], DP[i-1][j]);
					}
					
				}
			}
		}
		
		Arrays.sort(DP[n-1]); // 오름차순 정렬
		System.out.println(DP[n-1][n-1]);
			
	}
}

👨🏻‍💻 결과

 

 

📕 풀이 방법

 

DP[i][j] : (i,j)까지 내려왔을 때 경로에 있는 수들의 합 최대

 

2차원 배열 DP 값을 구한 뒤 배열 DP 마지막 줄을 정렬하여 최대값을 뽑아주면 됩니다.

 

 

🔗 링크

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

1932번: 정수 삼각형