[백준] 1149번 - RGB거리 java

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

 

난이도 : S1

Tag : DP

풀이 일자 : 2025-03-09

---

문제 탐색하기

N: RGB거리에 존재하는 모든 집의 개수 (2 <= N <= 1,000)

N개의 줄: N번째 집을 빨강, 초록, 파랑으로 칠하는 비용 (1 <= 비용 <= 1,000)

 

조건

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

조건을 정리하면 모든 집의 색은 인접한 집과 색깔이 달라야 합니다.

이 조건을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구하면 됩니다.

가능한 시간복잡도

0.5초이므로 시간 복잡도가 5000만 이하여야 합니다.

브루트포스(완전탐색)로 풀 경우 O(3^n)이 걸리고 N이 17만 되어도 약 1억 3천만의 연산이 필요하므로 적합지 않습니다. 

 

DP로 풀 경우 시간복잡도가 O(N)으로 가능하기 때문에 O(1000) 이내로 충분히 문제를 해결 가능합니다.

알고리즘 선택

DP를 선택하겠습니다.

 

각 집은 빨강, 초록, 파랑으로 칠할 수 있으며, 이전 집의 색깔과 겹쳐서는 안 됩니다.

그러므로 N번째 집이 빨강일 경우, 파랑일 경우, 초록일 경우의 최소 비용을 계산하면 점화식으로 만들 수 있습니다.

N번째 집이 빨강이면 -> 이전집은(초록, 파랑)

N번째 집이 파랑이면 -> 이전집은(초록, 빨강)

N번째 집이 초록이면 -> 이전집은(빨강, 파랑) 이여야 합니다.

 

이 상황을 점화식으로 만들어보면 아래처럼 나오게 됩니다.

//현재 집을 칠하는 최소 비용 = 이전 집에서 가능한 색 중 최소 비용 + 현재 집 비용
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] //파랑

기저사례

이제 초기값을 구해야 합니다.

먼저 첫 번째 집에서의 색을 칠하는 비용은 이전 집에 영향을 받지 않으므로 아래처럼 설정할 수 있습니다.

dp[0][0] = cost[0][0]
dp[0][1] = cost[0][1]
dp[0][2] = cost[0][2]

 

이후 모든 dp[i][j]값이 구해졌을 때 마지막 집에서 최소 비용을 골라주면 됩니다.

Math.min(dp[n-1][0], Math.min(dp[n-1][1], dp[n-1][2])

 

---

코드 설계하기

1. N의 크기를 입력받고 cost[][]배열을 초기화합니다.
2. 첫 번째 집의 색깔별 비용을 dp[0][0], dp[0][1], dp[0][2]에 각각 저장합니다.
3. 점화식을 사용하여 dp[][]를 채웁니다.
4. dp[N-1][0], dp[N-1][1], dp[N-1][2]값을 확인 후 최소 비용을 출력합니다. 

---

정답코드

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

class Main {
    final static int MAX_COLOR = 3;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int[][] cost = new int[n][MAX_COLOR];
        int[][] dp = new int[n][MAX_COLOR];
        
        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<MAX_COLOR; 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];
        
        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 ans = Math.min(dp[n-1][0], Math.min(dp[n-1][1], dp[n-1][2]));
        System.out.println(ans);
    }
}