[JAVA] 백준 (실버1) 4883번 삼각 그래프

링크

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

---

입력 예제

4
13 7 5
7 13 6
14 3 12
15 6 16
0

---

출력 예제

1. 22

---

풀이

이 문제에서 주의할 점은 경로가 양수가 아니라 정수라는 점이다. 그래서 무조건 다음 행으로 내려가는게 최소 비용이 아닐 수 있다. 문제의 제시된 그래프대로 다이나믹 프로그래밍을 수행한다.

dp배열을 다음과 같이 정의한다.

dp[i][j]: i행 j열까지의 경로의 최소 비용

첫번째 행의 중앙부터 시작하니까 다음과 같이 초기화를 한다. 이때 (0, 0)은 접근할 수 없으므로 비용의 최댓값에서 1을 더한 값을 저장한다.

dp[0][0] = 1001;
dp[0][1] = graph[0][1];
dp[0][2] = graph[0][1] + graph[0][2];

그리고 문제의 그래프 방향대로 dp배열을 채워나간다.

for (int i = 1; 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 - 1][0], dp[i - 1][1]),
            Math.min(dp[i - 1][2], dp[i][0])
    );
    dp[i][2] += Math.min(
            Math.min(dp[i - 1][1], dp[i - 1][2]),
            dp[i][1]
    );
}

전체 코드

//백준
public class Main {

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int num = 1;

        while (true) {
            int N = Integer.parseInt(br.readLine());
            if (N == 0) {
                break;
            }

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

            dp[0][0] = 1001;
            dp[0][1] = graph[0][1];
            dp[0][2] = graph[0][1] + graph[0][2];

            for (int i = 1; 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 - 1][0], dp[i - 1][1]),
                        Math.min(dp[i - 1][2], dp[i][0])
                );
                dp[i][2] += Math.min(
                        Math.min(dp[i - 1][1], dp[i - 1][2]),
                        dp[i][1]
                );
            }

            sb.append(num).append(". ")
                    .append(dp[N - 1][1]).append("\n");
        }

        System.out.println(sb);
    }
}