[Java] 1149번: RGB거리 Silver 1

문제 링크

보자마자 DFS가 생각났다..
이러면 안 되니까 DP식으로 생각해보자..!

고민하다보니, 전에 풀었던 2579번: 계단 오르기 Silver 3 문제랑 뭔가 비슷하다는 느낌이 들었다.
저 문제에서는 한 번에 한 개 또는 두 개의 계단을 오를 수 있었고, 연속한 세 개의 계단을 밟으면 안 됐다.

이 문제는 인접한 집에 대해서는 다른 색을 칠해야 하기에 이전 결과를 고려해서, 다음 값을 고려해야한다는 점이 비슷한 느낌이었다.

그렇다고 해서 방법이 바로 떠오르지는 않았다..

예시들이 하필 최소값만 고르면 바로 답이 나오는 예시들로 구성돼 있었다.

그 중에서 마지막 예시였던 것을 보니 최소값만 골라서는 답이 나오지 않는 것이 있었다.

8
71 39 44
32 83 55
51 37 63
89 29 100
83 58 11
65 13 15
47 25 29
60 66 19

최소값만 골라서 4번 째 집을 결정하게 된다면 29를 고를 수 없게 된다.
네 번째에서 무조건 29를 골라야만 최소값인 답을 구할 수 있다.

그러면 어떻게 해야 29를 선택하도록 할 수 있을까?

우선은 DP 배열을 N번 째 집까지의 최소비용으로 생각하자.

그리고 29를 고르려면 이전에 51이나 63을 골랐어야 했다.
세 번째 집까지 생각해보면, 39 + 32 + 37이 맞다.
그런데 네 번째 집까지 생각해보면, 39 + 32 + 63 + 29가 맞다.
이 때 세 번째 집의 결과가 달라졌다. 물론 각각 어떤 집을 칠했는지를 모두 요구하고 있지 않기에, 이전까지의 최소합만 기억하고 있으면 되는 것이다.

그렇다면 DP배열에는 일차원배열로 만들어서 최소값 하나만 기억할 게 아니라, 각 케이스들을 모두 기억하고 있어야 한다는 말이다.

그렇다면 이전 값에 무엇을 선택했는지 기억하기 위해서 플래그 값이 있어야 한다는 것이다.

근데 그럴 거면 그냥 모든 케이스를 누적합하는 거랑 마찬가지 아닐까..? 라는 생각이 들었다.

그렇게 생각하니, 그냥 첫 배열을 입력받을 때 그 배열을 dp 배열로 생성하고, 거기에 house를 칠하는 비용을 모두 저장해서 본인과 같은 색을 제외한 나머지 두 색 중에서 더 작은 값을 계속 누적합하면 답이 나오지 않을까 싶었다..

그리고 그렇게 푸니 정답이었다..

점화식은 이렇다.

dp[i][0]=cost[i][0]+min(dp[i−1][1],dp[i−1][2])
dp[i][1]=cost[i][1]+min(dp[i−1][0],dp[i−1][2])
dp[i][2]=cost[i][2]+min(dp[i−1][0],dp[i−1][1])

answer=min(dp[N−1][0],dp[N−1][1],dp[N−1][2])

이게 Silver 1인데도 뭔가 계단 오르기 문제보다는 쉽다는 느낌이 들었다.

정답

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

        // N 입력 받기
        int N = Integer.parseInt(br.readLine());

        // 배열 입력 받기
        int[][] dp = new int[N][3];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 3; j++) {
                dp[i][j] = Integer.parseInt(st.nextToken());
            }
        }

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

        // 출력
        System.out.println(Math.min(Math.min(dp[N - 1][0], dp[N - 1][1]), dp[N - 1][2]));
    }
}