[백준] 4883번. 삼각 그래프(JAVA)

문제

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

---

풀이(20분)

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));
        StringTokenizer st;

        StringBuilder sb = new StringBuilder(); // 정답 출력을 위한 객체 생성
        int k = 1;

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

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

            // 초기화
            arr[0][2] += arr[0][1];
            arr[1][0] += arr[0][1];
            arr[1][1] += Math.min(arr[1][0], Math.min(arr[0][1], arr[0][2]));
            arr[1][2] += Math.min(arr[1][1], Math.min(arr[0][1], arr[0][2]));

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

            int answer = arr[n - 1][1];
            sb.append(k).append(". ").append(answer).append("\n");
            k++;
        }

        System.out.print(sb);
    }
}

---

문제 풀이 전략

 

풀이만 보면 사실 단순한 dp이다.

하지만, 중요했던 부분은 dp를 짤 때 모든 상황에 대한 완벽한 고려를 해야 한다는 것이다.

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

 

이 그림만 봤을 때는 단순하게 0번열부터 좌우, 3방향, 좌우로만 min을 계산해도 최솟값을 찾아낼 수 있지 않을까? 싶다.

왜냐하면 어차피 삼각형을 그리며 내려온다고 해도 중복되게 거치기만 하는 느낌이기 때문이다.

 

하지만 실제 문제 풀이 시에는 삼각형을 거쳐 내려오는 것에 대한 모든 고려를 해야한다.

 

예를 들어 2행 2열의 12가 있는 자리를 생각해 보자.

만약 13,6 이 아닌 5000,5000이었다면 최솟값이 적용될까? 아니다. 7 -> 7 -> 14 -> 3을 거쳐서 오는 게 최소가 된다.

그렇기에 문제를 정확하게 분석하고 dp를 세워야 할 것이다!!