백준 4883번 자바 : 삼각 그래프

다이나믹 프로그래밍

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 { 
    static int N;
    static long[][] graph;
    static long[][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int now = 0;

        while(true) {
            N = Integer.parseInt(br.readLine());
            if(N==0) return;
    
            graph = new long[N][3];
            dp = new long[N][3];

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

            // 0행
            dp[0][0] = Integer.MAX_VALUE;
            dp[0][1] = graph[0][1];
            dp[0][2] = dp[0][1] + graph[0][2];

            // 1행~
            for(int i=1; i<N; i++) {
                // 0
                dp[i][0] = Math.min(dp[i-1][0], dp[i-1][1]) + graph[i][0];

                // 1
                dp[i][1] = Math.min(Math.min(Math.min(dp[i-1][0], dp[i-1][1]), dp[i-1][2]), dp[i][0]) + graph[i][1];

                // 2
                dp[i][2] = Math.min(Math.min(dp[i-1][1], dp[i-1][2]), dp[i][1]) + graph[i][2];
            }

            System.out.println(++now+ ". " + dp[N-1][1]);
        }
    }


}