[Algorithm/Java] 백준 1149번 - RGB거리

---

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

---

📌 문제

문제 유형

• DP

📘 문제 설명

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다.

각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

📥 입력

3
26 40 83
49 60 57
13 89 99

📥 출력

96

🔍 문제 풀이

문제 이해하기

문제 이해가 어려웠는데 Stranger’s LAB 님 블로그를 보고 힌트를 얻었다.

1. 1번집 R, G, B 중 최솟값 찾기 -> R이 최솟값 (26)
2. 2번집은 1번 집에서 선택한 R을 제외한 G, B중 최솟값 찾기 -> B가 최솟값 (26 + 57 = 83)
3. 3번 집은 2번 집에서 선택한 B를 제외한 R, G 중 최솟값 찾기 -> R이 최솟값 (13 + 83 = 96)

• 이렇게 1번 집의 R, G, B 중 최솟값을 선택한다고 가정하면, 이후 집들은 이전 집에서 선택한 색을 제외한 두 색 중 최소 비용을 선택해 누적해 나갈 수 있다.

• 하지만 이 방식은 하나의 경로만 따라가는 방식이기 때문에, 전체 색 조합 중에서 최적의 해를 보장하지 않는다.

• 따라서 이 과정을 모든 칸, 모든 색의 경우에 대해 반복하며, 이전 집에서 자신과 다른 두 색 중 최소 비용을 누적하는 방식으로 전체 경우를 고려해야 올바른 정답을 구할 수 있다.

이 과정을 모든 집, 모든 색의 경우에 대해 반복 수행하면, 각 위치마다 해당 색으로 칠할 경우의 최소 비용이 누적되며 최종적으로 아래와 같은 DP 테이블이 구성된다.

집 번호	빨강(dp[i][0])	초록(dp[i][1])	파랑(dp[i][2])
0번 집	cost[0][0]	cost[0][1]	cost[0][2]
1번 집	min(dp[0][1], dp[0][2]) + cost[1][0]	min(dp[0][0], dp[0][2]) + cost[1][1]	min(dp[0][0], dp[0][1]) + cost[1][2]
2번 집	min(dp[1][1], dp[1][2]) + cost[2][0]	min(dp[1][0], dp[1][2]) + cost[2][1]	min(dp[1][0], dp[1][1]) + cost[2][2]
…	…	…	…
N번 집	min(dp[N-1][1], dp[N-1][2]) + cost[N][0]	min(dp[N-1][0], dp[N-1][2]) + cost[N][1]	min(dp[N-1][0], dp[N-1][1]) + cost[N][2]

마지막 집(n번)까지 칠한 뒤, 그 집이 어떤 색이든 상관없이 전체 최소 비용을 구해야 하므로 마지막 줄의 세 값 중 최솟값이 정답이다.

min(dp[N-1][0], dp[N-1][1], dp[N-1][2])

💻 전체 코드

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

        int n = Integer.parseInt(br.readLine());
        int[][] cost = new int[n][3];
        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++){
                cost[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 초기화
        dp[0][0] = cost[0][0];
        dp[0][1] = cost[0][1];
        dp[0][2] = cost[0][2];

        // 두번째 집부터 DP
        for(int i=1; i<n; i++){
            dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + cost[i][0];
            dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + cost[i][1];
            dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + cost[i][2];
        }

        // 최소비용 출력
        int result = Math.min(Math.min(dp[n - 1][0], dp[n - 1][1]), dp[n - 1][2]); // 세 수를 비교하기 위해 두 번 호출
        System.out.println(result);
    }
}