[백준] 1149. RGB거리

문제 정의

이 문제는 모의 코테를 하면서 풀었던 1번 문제였다.
당시에는 틀렸고 끝나고 나서 복기하는 과정을 거치고 다시 풀어냈다.

문제 풀이

틀린 버전

문제를 보고 든 생각은 일단 그리디 문제는 아니라는 생각이 들었다.
최솟값을 항상 고른다고 해서 그 값이 최적해가 되지 않을 수 있었기 때문이다.
반례를 들어보면 (1, 10, 100), 다음 칸이 (10, 1000, 1001) 같은 경우가 있겠다.
1을 먼저 고르면 그 뒤의 경우에서는 R을 고르지 못하기에 10을 못 고른다. 그러면 1001이 되게 된다.(최적해가 아님)


그래서 DP인가 싶었는데, 세 가지 색깔이라는 조건 때문에 수열처럼 하나의 상태가 정해지지 않게 되고,
그러면 앞선 결과를 뒤에 사용해야 하는 DP가 아니라는 생각도 들었다.(여기서 틀린 것이다.)


내가 내린 결론은 백트래킹을 해서 최대한 가지치기를 하며 완전탐색을 돌리는 것이었다.
결국 시간초과가 발생했다.
→ 내가 틀린 이유는 시간 제한을 제대로 생각하지 않은 것과 DP에 대해 잘 몰랐던 것 2가지였다.
아래는 틀린 버전의 코드이다.

// 틀린 완전탐색 버전 코드
public class P1149 {
    static int[][] cost;
    static int N;
    static int result = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        cost = new int[N][3];

        for (int i = 0; i < N; i++) {
            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());
        }

        dfs(0, 0, -1);

        bw.write(result + "\n");

        bw.flush();
        bw.close();
        br.close();
    }

    static public void dfs(int depth, int costSum, int prevColor) {
        if (depth == N) {
            if (result > costSum) {
                result = costSum;
            }
            return;
        }
        if (costSum > result)
            return;

        for (int i = 0; i < 3; i++) {
            if (prevColor != i) {
                dfs(depth + 1, costSum + cost[depth][i], i);
            }
        }
    }
}

맞는 버전

DP를 사용해야 했다. 여러 상태를 고를 수 있어서 R과 G와 B를 고른 뒤 각각의 상태를 따로 관리하는 것이 포인트였다.
그래서 첫 번째로 R을 고른 버전, 두 번째는 G를 고른 버전, 세 번째는 B를 고른 버전으로 관리하여 3가지 중 가장 낮은 값을 가지는 것을 찾아야 했다.

코드

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

public class P1149 {
    static int[][] cost;
    static int N;
    static int result = 0;
    static int[][] memo;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        cost = new int[N][3];
        memo = new int[N][3];

        for (int i = 0; i < N; i++) {
            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();

        bw.write(result + "\n");

        bw.flush();
        bw.close();
        br.close();
    }

    public static void dp() {

        memo[0][0] = cost[0][0];
        memo[0][1] = cost[0][1];
        memo[0][2] = cost[0][2];

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

        result = Math.min(memo[N - 1][0], memo[N - 1][1]);
        result = Math.min(result, memo[N - 1][2]);
    }

}