[백준]1149 RGB거리

역대급 어려웠다.
문제 이해 자체가 안돼서 풀이를 봐도 못 풀겠었던 애증의 dp 문제..

package baekjoon;

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

public class Main_1149 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[][] home = new int[N][3];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            home[i][0] = Integer.parseInt(st.nextToken());
            home[i][1] = Integer.parseInt(st.nextToken());
            home[i][2] = Integer.parseInt(st.nextToken());
        }

        int minLocation = -1;
        int sum = 0;
        for (int i = 0; i < home.length; i++) {
            int minCost = (minLocation==2) ? home[i][0] : home[i][minLocation+1];
            for (int j = 0; j < home[i].length; j++) {
                if(minCost >= home[i][j] && minLocation!=j) {
                    minCost = home[i][j];
                    minLocation = j;
                }
                System.out.print(home[i][j]+"("+minCost+"/"+minLocation+") ");
            }
            sum += minCost;
            System.out.println();
        }
        System.out.println(sum);
    }
}

처음엔 이렇게 접근했다

[input]
3
26 40 83
49 60 57
13 89 99

[output]
26(26/0) 40(26/0) 83(26/0) 
49(60/0) 60(60/1) 57(57/2) 
13(13/0) 89(13/0) 99(13/0)

96

첫 줄에서 가장 작은 값의 위치를 찾고
다음줄에 그 위치를 제외한 가장 작은 값을 더하고 위치를 갱신하고
또 그 다음줄에서 그 위치를 제외한 가장 작은 값을 더하고
.
.
.

몇 개의 테스트 케이스에선 맞았지만 이건 잘못된 방법이었다는 것을 깨달았다.
반례 케이스로 이런 데이터가 있을 경우

3
1 10 10
1 100 100
1 1 1

나의 소스는 맨 첫줄의 최솟값을 찾아 1+100+1=102 가 될테지만
정답은 맨 첫줄의 10부터 시작하여 10+1+1=12 가 되어야 한다.

= 즉 각 줄의 최솟값을 찾는 것이 아닌 모든 줄의 최솟값을 도출하는 경우를 찾아야 한다는 뜻 😭

결국 풀이의 도움을 받았다. dp는 허무한게 코드가 되게 짧다. 현타를 심하게 느끼게 만드는 dp ..

정답코드는 이렇다

package baekjoon;

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

public class Main_1149 {
    static int[][] dp;
    static int[][] cost;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        dp = new int[N][3];
        cost = new int[N][3];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            cost[i][0] = Integer.parseInt(st.nextToken());
            cost[i][1] = Integer.parseInt(st.nextToken());
            cost[i][2] = Integer.parseInt(st.nextToken());
        }
        // 첫째줄 집 값으로 dp 값 초기세팅
        dp[0][0] = cost[0][0];
        dp[0][1] = cost[0][1];
        dp[0][2] = cost[0][2];

        System.out.println(Math.min(paint(N-1, 0), Math.min(paint(N-1, 1), paint(N-1, 2))));

    }
    static int paint(int N, int color) {
        if(dp[N][color] == 0) {
            if(color == 0) {
                // 빨
                dp[N][color] = Math.min(paint(N-1, 1), paint(N-1, 2))+cost[N][0];
            } else if(color == 1) {
                // 초
                dp[N][color] = Math.min(paint(N-1, 0), paint(N-1, 2))+cost[N][1];
            } else {
                // 파
                dp[N][color] = Math.min(paint(N-1, 0), paint(N-1, 1))+cost[N][2];
            }
        }
        return dp[N][color];
    }
}

이해하면 쉽다. 같은 색깔이 아닌 값 중에 전줄의 최솟값과 현재색깔의 비용을 더해 저장해준뒤 각 색깔의 최소를 비교해서 출력하면 된다.
설명이 영 허술하지만.. 무튼.. 그렇다..
자신감 -1