[백준, 자바] 1932번- 정수 삼각형

문제 링크
https://www.acmicpc.net/problem/1932

코드

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[][] dp = new int[N][N];

        for(int i = 0; i < N; i++) {
            String[] str = br.readLine().split(" ");
            for(int j = 0; j <= i; j++) {
                dp[i][j] = Integer.parseInt(str[j]);
            }
        }

        for(int i = 1; i < N; i++) {
            for(int j = 0; j <= i; j++) { // 실패했었음
                int leftTop = (j-1) < 0 ? 0 : dp[i - 1][j - 1];
                int rightTop = dp[i - 1][j];
                int me = dp[i][j];

                //dp에 저장한다. leftTop과 rightTop중에 본인(input[i][j])을 더한 값이 더 큰 쪽을
                dp[i][j] = Math.max(leftTop + me, rightTop + me);
//                System.out.println("dp[i] = " + dp[i][j]);
            }
        }

        int max = Integer.MIN_VALUE;
        for(int i = 0; i < N; i++) {
            max = Math.max(max, dp[N-1][i]);
        }
        System.out.println(max);
    }
}

풀이
위에서부터 왼쪽 대각선 또는 오른쪽 대각선으로 내려오면서 최댓값을 구하는 케이스다.
같은 층을 선택할 수 없다.
이 문제는 전형적인 dp로서 RGB류의 문제가 생각이 났다. 나동빈 작가의 파이썬 알고리즘 책으로도 봤었는데
(정말 기가막히는 레전드 책이다)

아래 입장에서 이전 방향의 값이랑 본인 값을 더하면 된다. 다만 Math.max(왼쪽대각선+본인, 오른쪽대각선+본인)이 되어야 겠지.

백준 예제를 예로 들면,

여기서 탐색 범위를 정하는데 좀 헤맸고, 저 삼각형 입력값을 배열로 어떻게 설정할 지가 감이 안 잡혔었다.
삼각형 입력값의 경우 초반에는

  int[][] input = {
//            {0, 7, 0, 0, 0, 0},
//            {0, 3, 8, 0, 0, 0},
//            {0, 8, 1, 0, 0, 0},
//            {0, 2, 7, 4, 4, 0},
//            {0, 4, 5, 2, 6, 5}
//        };

이런 구조로 생각해서 더미 데이터를 만들고 코딩을 했는데, BufferedReader로 바꾸는 과정에서 저대로 값을 초기화하는 게 어려워서 최종적으로 아래처럼 초기화되고, for문 범위를 바꿨다.

/**
* int[][] dp = {
* {7, 0, 0, 0, 0},
* {3, 8, 0, 0, 0},
* {8, 1, 0, 0, 0},
* {2, 7, 4, 4, 0},
* {4, 5, 2, 6, 5}
*/

j는 i보다 작거나 같아야 하고, j-1은 0부터 시작하는 j라서 -1일 경우에 그냥 값 자체를 0으로 셋팅해야 하더라.

 for(int j = 0; j <= i; j++) { // 실패했었음
                int leftTop = (j-1) < 0 ? 0 : dp[i - 1][j - 1];