[Java] 4883번: 삼각 그래프 Silver 1

문제 링크

문제는 silver 1 치고는 너무 쉽다고 느껴져서, 아이패드에 그리지 않고 바로 작성했다.
그냥 각 경로별로 올 수 있는 이전 케이스들을 고려해서 최솟값으로 갱신해주면 된다!

그러나~...

1. 초기값 설정에서 헤매고,,
2. 값이 음수도 존재한다는 사실을 몰라서 헤매고,,
3. dp를 2행부터 실행해야 하는 걸 알고 있었는데, 초기값을 1로 둬서 한참 헤매고,,

쉬운 문제를 한 시간 넘게 썼다..😢

정답

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = 0, N;

        while ((N = Integer.parseInt(br.readLine())) != 0) {

            tc++;

            // 배열 입력 받기
            int[][] dp = new int[N][3];
            for (int i = 0; i < N; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int j = 0; j < 3; j++) {
                    dp[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            // 초기값 설정
            dp[1][0] += dp[0][1];
            dp[1][1] += Math.min(dp[1][0], dp[0][1] + Math.min(0, dp[0][2]));
            dp[1][2] += Math.min(dp[1][1], dp[0][1] + Math.min(0, dp[0][2]));

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

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

내일부턴 🥇골드 문제 풀 차례다!