BOJ_S1_1932

📁 [S1_1932] 정수 삼각형

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

public class Main {
    static StringTokenizer st;
    static int[][] arr;
    static int[][] dp;
    static int N;

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

        // 삼각형 크기
        N = Integer.parseInt(br.readLine());

        // 삼각형 값들
        arr = new int[N][N];

        dp = new int[N + 1][N + 1];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j <= i; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = N - 1; i >= 0; i--) {
            for (int j = i; j >= 0; j--) {
                // dp 배열에 2값을 비교해서 큰 값과 본인 값을 더해서 dp에 저장한다
                dp[i][j] = Math.max(dp[i + 1][j], dp[i + 1][j + 1]) + arr[i][j];
            }
        }
        System.out.println(dp[0][0]);
    }
}

🤔 나의 생각

DP 문제이다.
일단 N이 500개 까지 있기 때문에 DP로 푸는 것을 알았다.
그림을 그려보았을 때 한 행 밑에 값과 한 행 밑의 오른쪽 값과 비교해서 더 큰 값을 본인 값과 더해주면 되는 규칙을 발견하였다.
이진 트리의 구조라서 쉽게 이해할 수 있었다.
확실히 빨리 규칙을 찾는게 중요한 것 같다 !!