[BOJ] 4883 삼각 그래프 (JAVA)

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

4883번: 삼각 그래프

첫 번째 행, 첫 번째 열에서는 시작할 수 없음을 인지해야 합니다.

 

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

public class Main {
	
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;
    static int K = 1, N;
    static int[][] input, dp;
    static int[] dr = {  0, -1, -1, -1 };
    static int[] dc = { -1, -1,  0,  1 };

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

        while (true) {

            N = Integer.parseInt(br.readLine());

            if (N == 0) break;

            input = new int[N][3];
            dp = new int[N][3];
            for (int i = 0; i < N; i++) {
                Arrays.fill(dp[i], 123456789);
                st = new StringTokenizer(br.readLine(), " ");
                for (int j = 0; j < 3; j++) {
                    input[i][j] = Integer.parseInt(st.nextToken());
                }
            } // end of input

            dp[0][1] = input[0][1];
            dp[0][2] = input[0][1] + input[0][2];

            for (int i = 1; i < N; i++) {
                for (int j = 0; j < 3; j++) {
                    for (int from = 0; from < 4; from++) {
                        int pr = i + dr[from];
                        int pc = j + dc[from];

                        if (0 <= pc && pc < 3) dp[i][j] = Math.min(dp[i][j], dp[pr][pc] + input[i][j]);
                    }
                }
            }

            sb.append(K++).append(". ").append(dp[N - 1][1]).append("\n");

        }

        System.out.print(sb);

    }
	
}