[백준] 정수 삼각형 (1932번 JAVA) / 401 - 다이나믹 프로그래밍 1 (연습)

[백준] 정수 삼각형 (1932번 JAVA) / 401 - 다이나믹 프로그래밍 1 (연습)

---

[접근 방법]

 

이 문제는 상당히 유명한 DP 활용 문제이다.

 

1. 삼각형의 cost를 2차원 배열로 정의 한다.

2. cost 배열의 원소를 누적합 중 최댓값으로 갱신한다.

3. n 열의 값 (총 경로의 cost 누적합) 중 최댓값을 도출한다.

	int max = 0;
        for(int i=1; i<n+1; i++){
            max = Math.max(max, cost[n][i]);
        }

---

[JAVA 코드]

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main{

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 삼각형의 크기 n (1 ≤ n ≤ 500)
        int n = Integer.parseInt(br.readLine());

        // (0 ~ n) X (0 ~ n)
        int[][] cost = new int[n+1][n+1];
        // 각 경로의 cost를 2차원 배열에 입력 받는다.
        for(int i=1; i<n+1; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=1; j<=i; j++){
                cost[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 위치(i, j)로 부터, (i-1, j-1) 과 (i-1, j) 중 최댓값을 누적한다. 
        for(int i=1; i<n+1; i++){
            for(int j=1; j<=i; j++){
                cost[i][j] = Math.max( cost[i-1][j-1] , cost[i-1][j] ) + cost[i][j];
            }
        }

        // n 열에 위치한 경로의 누적합들 중 최댓값을 도출한다.
        int max = 0;
        for(int i=1; i<n+1; i++){
            max = Math.max(max, cost[n][i]);
        }

        bw.write(max + "\n");
        bw.flush();
        bw.close();
    }
}