[백준] #1932 - 정수 삼각형

🔒문제 설명

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

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

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

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

입력

---

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

출력

---

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

🔑해결 아이디어

DP를 사용하는 문제를 구분할 수 있게 되었다.
이전의 계산 결과가 필요한 경우 대부분 부르트포스 OR DP를 활용하는 문제라고 생각하면 될 것 같다.
이번 문제에서 역시 누적 최대값을 구해야 했기 때문에 이전 계산 결과가 필요했다.
매 층마다 DP를 갱신하며, DP$[j]$번째 값은 이번층에서 $j$번째 원소로 끝나는 경우의 경로 최대값을 저장했다.

기억하기

자바 배열의 깊은 복사, 얕은 복사

이전 문제풀이에서 배열의 얕은 복사와 깊은 복사로 인해 어려움을 겪었다.
이후, 1차원 배열이나 객체의 경우 A.clone()의 함수 사용으로 쉽게 깊은 복사를 할 수 있다는 사실을 학습했다.

💻소스코드

import java.util.Arrays;
import java.util.Scanner;

public class BJ1932 {
    public static void main(String[] args) {
    
    // 입력 받기 //
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] triangle = new int[n][];
        for(int i = 0; i<n; i++){
            triangle[i] = new int[i + 1];
            for (int j = 0; j <= i; j++) {
                triangle[i][j] = sc.nextInt();
            }
        }
        int[] DP = new int[n];

	// DP 값 갱신 //
        for (int i = 0; i < n; i++) {
            int[] newDP = new int[i + 1];
            for (int j = 0; j <= i; j++) {
                if (j == 0)
                    newDP[j] = DP[0] + triangle[i][0];
                else if(j == i)
                    newDP[j] = DP[j - 1] + triangle[i][j];
                else{
                    int leftSum = DP[j - 1] + triangle[i][j];
                    int rightSum = DP[j] + triangle[i][j];
                    newDP[j] = leftSum > rightSum ? leftSum : rightSum;
                }
            }
            DP = newDP.clone();
        }

        int answer = DP[0];
        for (int i : DP) {
            if(i > answer)
                answer = i;
        }

        System.out.println(answer);
    }
}

추가 공부

• Java Stream