[백준/4883] 삼각 그래프 - JAVA

📌 문제

알고리즘 분류 : DP
난이도 : 실버1
출처 : 백준 - 삼각 그래프

🦧 문제 풀이 접근

DP로 문제를 해결 할 수 있다.
왼쪽, 가운대, 오른쪽을 각각 다르게 최소값을 구해 나간다.
이때 2번째 줄에 경우 0,0위치는 무시하고 최소값을 구하면 된다.

💻 code

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int cnt=0;
        while(true) {
            int N = Integer.parseInt(br.readLine());
            if(N==0)
                break;
            cnt++;
            int dp[][] = new int[N][3];
            StringTokenizer st = new StringTokenizer(br.readLine());
            dp[0][0] = Integer.parseInt(st.nextToken());
            dp[0][0] = Integer.MAX_VALUE;
            dp[0][1] = Integer.parseInt(st.nextToken());
            dp[0][2] = dp[0][1]+Integer.parseInt(st.nextToken());
            for(int i=1;i<N;i++) {
                st = new StringTokenizer(br.readLine());
                dp[i][0] = Integer.min(dp[i-1][0],dp[i-1][1])+Integer.parseInt(st.nextToken());
                dp[i][1] = Integer.min(Integer.min(dp[i][0],dp[i-1][0]),Integer.min(dp[i-1][1],dp[i-1][2]))+Integer.parseInt(st.nextToken());
                dp[i][2] = Integer.min(Integer.min(dp[i][1],dp[i-1][1]),dp[i-1][2])+Integer.parseInt(st.nextToken());
            }
            sb.append(cnt).append(". ").append(dp[N-1][1]).append("\n");
        }
        System.out.println(sb);
    }
}

🥇 결과

🎓 느낀점

0,0칸은 무시하는 것만 알면 쉽게 풀 수 있다.