방과후
ALGORITHM NOTE약 1분

BOJ 17404 - RGB거리 2

진화된 RGB거리

#algorithm#boj#gold#dp
아카이브로 돌아가기

문제 링크

문제

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

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

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

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

풀이

첫 집과 마지막 집의 색이 달라야 한다는 조건 때문에, 첫 집 색을 하나 고정하고 나머지를 DP로 채우는 방식이 잘 맞는다. 첫 집 색이 정해지면 이후는 일반 RGB 거리 문제와 같은 구조가 된다.

코드에서는 첫 집 색을 R, G, B로 각각 고정한 세 경우를 따로 돌린다. 고정하지 않은 색은 매우 큰 값으로 시작해 선택되지 않도록 만들고, 마지막 집에서는 첫 집과 같은 색을 제외한 값만 답 후보로 본다.

원형 제약을 세 번의 선형 DP로 푸는 문제다.

코드

java
import java.io.*;
import java.util.*;
 
public class Main {
 
    static int[][] cost;
    static int N, INF = 1000001;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        cost = new int[N + 1][3];
 
        for (int i = 1; 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());
        }
 
        int ans = solve();
        System.out.println(ans);
    }
 
    static int solve() {
        int[][] dp = new int[N + 1][3];
        int ans = INF;
 
        for (int start = 0; start < 3; start++) {
            for (int i = 0; i < 3; i++) {
                if (i == start)
                    dp[1][i] = cost[1][i];
                else
                    dp[1][i] = INF;
            }
 
            for (int i = 2; 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];
            }
 
            for (int i = 0; i < 3; i++)
                if (i != start)
                    ans = Math.min(ans, dp[N][i]);
        }
 
        return ans;
    }
 
}

복잡도

  • 시간 복잡도: O(N)O(N)
  • 공간 복잡도: 색 수 기준 상수 또는 O(N)O(N)

마무리

첫 집과 마지막 집이 이어지는 조건이 어려워 보이지만, 첫 색을 고정해서 세 번만 돌리면 된다. 원형 제약을 선형 DP로 바꾸는 관점이 핵심이다.