(Java) 백준 1149 - RGB 거리

처음 시도는 완전 탐색으로 시도했지만 50%에서 시간 초과가 나왔다.

N의 값이 1000 이하니 완전 탐색을 이용하면 시간 초과가 나오는 게 당연한 결과였다.

다른 방법을 생각해봤지만 떠오르지 않아서 검색을 통해 힌트를 참고했다.

 

처음에는 이 문제가 왜 DP를 이용하는지 이해가 잘 안되었다.

점화식도 떠오르지 않았고, 지금까지 풀었던 문제들과는 조금 달라서 그렇게 생각한 것 같다.

 

풀이 방법은 R, G, B를 0, 1, 2로 대응시키고 다음 집의 색상을 봐야 한다.

예를 들어 첫 번째 집이 0이라면 다음 집은 1 또는 2가 되어야 한다.

1과 2중에서 더 작은 값을 더해 n까지 배열을 만들면 된다.

마지막으로 배열의 세 값 중 가장 작은 값을 출력하면 된다.

 

DP로 풀 수 있는 문제지만 이전 집의 색상과 다른 색상 중 작은 값을 선택하는 면에서 그리디 같다고도 느껴졌다.

 

실패 코드 (완전 탐색)

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

public class Main {
    static int n;
    static int[][] arr;
    static int answer;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n][3];
        answer = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
            arr[i][2] = Integer.parseInt(st.nextToken());
        }
        // 첫번쨰 집 지정
        for (int i = 0; i < 3; i++) {
            cal(0, i, 0);
        }
        System.out.println(answer);
    }

    // 완전탐색 메서드
    static void cal(int idx, int preIdx, int price) {
        int result = price;
        result += arr[idx][preIdx];

        if (idx == n-1) {
            answer = Math.min(answer, result);
            return;
        }

        for (int i = 0; i < 3; i++) {
            if(preIdx != i) {
                cal(idx + 1, i, result);
            }
        }
    }
}

최종 코드(DP)

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][3];

        // 입력값 배열에 삽입
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
            arr[i][2] = Integer.parseInt(st.nextToken());
        }

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

        System.out.println(Math.min(Math.min(arr[n-1][0], arr[n-1][1]), arr[n-1][2]));

    }
}