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

📎 문제 출처

---

https://www.acmicpc.net/problem/1932

📌 문제 설명

---

❓ 풀이 방법

---

드디어 내 힘으로 동적계획법 문제를 처음 풀었다 ㅜㅜ
이 전까지는 생각해보다가 안돼서 다른 사람 풀이 참고하고 나서야 겨우 이해할 수 있었는데!!

이전에 풀었던 최소비용으로 RGB 집 색칠하는 문제랑 비슷해서 풀 수 있었다.

물론 재귀로 바로 못풀고 반복문으로 풀었다.

숫자들을 n x n 크기의 2차원 배열에 저장한다.

arr[i][i] 까지의 최대합은 왼쪽 위인 arr[i-1][j-1]까지의 최대합과 오른쪽 위인 arr[i-1][j]까지의 최대합에 arr[i][j]의 숫자를 더한 값이다.

마지막 줄까지 각각의 최대합을 구하고 나서 그중 최댓값을 구하면 그게 답이다.

cost[i][j] = max(cost[i-1][j-1] + cost[i-1][j]) + cost[i][j]

📌 Code

---

package com.ll;

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

public class Main {
    static int[][] cost;

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

        cost = new int[N][N];

        StringTokenizer st;

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

    	for(int i = 1; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(j == 0) cost[i][0] = cost[i-1][0] + cost[i][0];
                else {
                    cost[i][j] = Math.max(cost[i-1][j-1], cost[i-1][j]) + cost[i][j];
                }
            }
        }

        int max = Arrays.stream(cost[N-1]).max().getAsInt();
        System.out.println(max);

    }

}