[BOJ] 1932: 정수 삼각형(JAVA)

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

1932번: 정수 삼각형

문제

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

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

예제 입력 1 

5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

예제 출력 1 

30

 

---

[문제 풀이]

2차원 정수 배열 triangle 에 입력을 위에서부터 차례로 저장한다.

만약 n=3, 입력이 7 3 8 8 1 0 으로 주어졌다면,

triangle[0][0] = 7

triangle[1][0] = 3

triangle[1][1] = 8

triangle[2][0] = 8

triangle[2][1] = 1

triangle[2][2] = 0  으로 저장한다.

 

2차원 배열 sum에는 아래층으로 내려올때 선택된 수의 합의 최댓값을 저장할 것인데, 예를 들면 다음과 같다.

sum[0][0]은 triangle[0][0] 외에 선택할 수 있는 것이 없으므로, sum[0][0] = triangle[0][0]이다.

sum[0][0]만이 triangle[1][0]과 triangle[1][1]을 선택할 수 있으므로, sum[1][0] = triangle[1][0] + sum[0][0], sum[1][1] = triangle[1][1] + sum[0][0]이다.

triangle[2][0]을 선택할 수 있는 것은 sum[1][0]이 유일하므로 sum[2][0] = triangle[2][0] + sum[1][0] 이고,

triangle[2][1]을 선택할 수 있는 것은 sum[1][0]과 sum[1][1] 2개가 있다. 따라서 둘 중 더 큰 수를 sum[2][1]에 더해주어야 한다. 따라서 sum[2][1] = triangle[2][1] + Math.max(sum[1][0], sum[1][1])이다.

triangle[2][2]을 선택할 수 있는 것은 sum[1][1] 뿐이므로 sum[2][2] = triangle[2][2] + sum[1][1] 이다.

 

이로 보았을 때 규칙은 다음과 같다.

1. sum[i][j]에서, j가 0이면, 선택할 수 있는 상위층의 수는 sum[i-1][j]가 유일하다. 따라서 sum[i][j] = triangle[i][j] + sum[i-1][j] 이다.

2. j가 n-1이면, 선택할 수 있는 상위 층은 sum[i-1][j-1]이 유일하다. 따라서sum[i][j] = triangle[i][j] + sum[i-1][j-1] 이다.

3. 위의 어느 경우에도 속하지 않는 j 값이라면 선택할 수 있는 상위 층은 sum[i-1][j], sum[i-1][j-1] 2가지 이다. 따라서 둘 중 더 큰 수를 더해주어야 하므로 sum[i][j] = triangle[i][j] + Math.max(sum[i-1][j], sum[i-1][j-1]) 이다.

 

sum[n-1][0]~sum[n-1][n-1]에는 각 마지막 행의 해당 위치의 수를 선택했을 때 얻을 수 있는 최댓값들이 저장되어있다. 따라서 마지막 층에 저장된 sum값 중 가장 최댓값을 찾아 반환하면 선택된 수의 합이 최대가 되는 경로를 구할 수 있다.

 

[코드]

import java.util.*;
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
         int n = sc.nextInt();
         int[][] triangle = new int[n][n];
         long[][] sum = new long[n][n];
    
         for(int i=0;i<n;i++) {
             for(int j=0;j<=i;j++) 
                 triangle[i][j] = sc.nextInt();
         }
    
    
    
         for(int i=0;i<n;i++) {
             for(int j=0;j<=i;j++) {
                 if(i==0&&j==0)
                     sum[i][j] = triangle[0][0];
                 else {
                     if(j==0)
                         sum[i][j] = triangle[i][j]+ sum[i-1][j];
                     else if(j==i)
                         sum[i][j] = triangle[i][j] + sum[i-1][j-1];
                     else
                         sum[i][j] = triangle[i][j] + Math.max(sum[i-1][j], sum[i-1][j-1]);

                 }
             }
         }
         long max = Long.MIN_VALUE;
         for(int i=0;i<n;i++) {
             if(max<sum[n-1][i])
                 max=sum[n-1][i];
         }
         System.out.println(max);
   
    }
}