[백준/1932] 정수 삼각형 (실버 1) JAVA

dp스럽게 풀면 된다.

예를 들어 front 배열이 1,2,3 이고 next배열이 2,3,4,5 라면
next배열을 기준으로 생각한다. next배열의 첫번째와 끝 인덱스는 front배열의 첫번째와 끝 인덱스로 조회해서 더해서 새롭게 업데이트될 front_임시 배열에 append한다. 나머지는 front[index-1], front[index] + next[index]의 최댓값을 저장한다. 이렇게 dp로 하여금 이전 계산을 누적시켜 마지막에 배열의 max를 주어 답을 구한다.

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int length = sc.nextInt();
        sc.nextLine();
        Object[] process = new Object[length];

        for (int i=0; i<length; i++) {
            process[i] = getArray(sc);
        }
        int[] front = (int[]) process[0];

        for (int i=0; i<length-1; i++) {
            int[] back = (int[]) process[i+1];

            int[] dp = new int[back.length];
            for (int j=0; j<back.length; j++) {
                if (j==0) {
                    int newNum = front[j] + back[j];
                    dp[j] = newNum;

                } else if (j == back.length -1) {
                    int newNum = front[j-1] + back[j];
                    dp[j] = newNum;

                } else {
                    // 좌우 최댓값 구하기
                    int left = front[j-1] + back[j];
                    int right = front[j] + back[j];
                    int newNum = Math.max(left, right);
                    dp[j] = newNum;

                }
            }
            front = dp;
        }
        System.out.println(Arrays.stream(front).max().getAsInt());
    }

    public static int[] getArray(Scanner sc) {
        String input = sc.nextLine();
        String[] inputArray = input.split(" ");
        int[] numbers = new int[inputArray.length];
        for (int i = 0; i < inputArray.length; i++) {
            numbers[i] = Integer.parseInt(inputArray[i]);
        }

        return numbers;
    }
}