[BOJ][Java] 1932번 - 정수 삼각형

문제

백준 1932번 문제: 정수 삼각형

문제 설명

각 층의 모든 칸마다 최댓값을 저장하면서 동적 계획법으로 푸는 문제

최대값을 찾기 위해서는 이전 열에서 최대값을 더해 나가야 한다.
문제의 예제로 이해를 해보자

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

맨 위의 수인 7은 제일 상단에 위치해 3과 8에 각각 7을 더해주면 된다.
그럼 10과 15가 되어 밑의 수들에게 선택을 받게 된다.
하지만 셋째줄의 맨 처음에 있는 8과 0은 선택의 여지가 없이 위의 수를 더해야 한다.
1은 10과 15 중 큰 수인 15를 선택할 수 있다.
이를 이용하여 큰 수를 축적해 나갈 수 있다. 아래 축적된 수를 보자.

        7
     10   15
   18  16   15
 20  25  20   19
24  30  27  26  24

가장 밑에 줄에 가장 큰 수는 30이라 30이 반환되면 맞는 답이다.
그러면 이전 문제인 RGB거리와 같게 풀면 되겠다.
앗 그런데 위에서 확인한 것과 같이 양 끝에 있는 수들은 선택의 여지가 없었다.
그러면 예외 처리가 필요하겠다. 예외처리는 다양하게 할 수 있다.
그 중 내가 찾은 방법은 2가지이다.

1. 양 끝의 수일 때는 최대값이 아닌 그냥 그 수를 선택해 더하게 하는 방법
2. 2차원 배열의 인덱스를 1씩 크게 만들어 0과 비교하면 자연적으로 하나의 값을 선택하게 하는 방법

나는 2번 방법으로 풀었다. 아래의 표를 보자.
노란색은 현재 큰 값을 선택하는 수이다.
파란색은 선택받아야 하는 대각선의 두 수이다.
0으로 0번 인덱스가 채워져 있기 때문에 자연적으로 7을 선택하게 된다.
마찬가지로 1번 라인인 7도 위에 0밖에 없기 때문에 0을 더하면 자기 자신이 된다.

이런 방식으로 반복문을 돌면 최대 누적값이 가장 아래 라인에 저장되고 이 값들 중 최대값을 구하면 된다.
아래는 이를 작성한 코드이다.

성공 코드

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int nums[][] = new int[n+1][n+1];
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= k; i++) {
                nums[k][i] = sc.nextInt();    
            }
        }
        sc.close();

        for (int l = 1; l <= n; l++) {
            for (int j = 1; j <= l; j++){
                nums[l][j] += Math.max(nums[l-1][j], nums[l-1][j-1]);
            }
        }

        int max = 0;
        for (int i = 0; i <= n; i++) {
            max = (nums[n][i] > max) ? nums[n][i] : max;
        }

        System.out.print(max);
    }
}