[BaekJoon] 17404번: RGB거리 2

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

17404번: RGB거리 2

 

 

 

 

 

원형을 이루는 집들 간에 RGB 의 색으로 집을 색칠 할 때의 최소 비용을 구하는 문제

고려할 점은 원형을 이루고 있고 서로 인접한 집들은 같은 색을 가지면 안된다는 점이다. 

 

 

다이나믹 프로그래밍으로 풀 수 있고 점화식을 

dp[i][0] = i - 1 번째 집까지 색칠한 최소값 + i 를 Red 로 칠했을 때의 값 

dp[i][1] = 위와 동일 + i 를 Green 으로 칠했을 때의 값

dp[i][2] = 위와 동일 + i 를 Blue 로 칠했을 떄의 값

 

으로 표현할 수 있다. 

 

 

0번째의 집의 색을 고정하고 dp[N-1]를 구할 때 같은 색일 경우를 피해주면 된다. 

 

반복문을 3번 돌려서 0번째 집을 R, G, B 일때로 각각 초기값을 세팅하고 고정 색이 정해졌다면 나머지 색은 INF 로 설정한다. 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int[][] RGB;
    static int[][] dp;
    static int N;
    static int MIN;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        RGB = new int[N][3];
        dp = new int[N][3];
        MIN = 987654321;
        
        for(int i = 0; i<N; i++) {
            String[] input = br.readLine().split(" ");
            RGB[i][0] = Integer.parseInt(input[0]);
            RGB[i][1] = Integer.parseInt(input[1]);
            RGB[i][2] = Integer.parseInt(input[2]);
        }
        
        // i : 0번째 집을 색칠 할 R, G, B 선택
        for(int i = 0; i<3; i++) {
            if (i == 0) {
                dp[0][0] = RGB[0][0];
                dp[0][1] = 987654321;
                dp[0][2] = 987654321;
            } else if (i == 1) {
                dp[0][0] = 987654321;
                dp[0][1] = RGB[0][1];
                dp[0][2] = 987654321;
            } else if (i == 2) {
                dp[0][0] = 987654321;
                dp[0][1] = 987654321;
                dp[0][2] = RGB[0][2];
            }
            
            for(int j = 1; j<N; j++) {
                dp[j][0] = Math.min(dp[j-1][1], dp[j-1][2]) + RGB[j][0];
                dp[j][1] = Math.min(dp[j-1][0], dp[j-1][2]) + RGB[j][1];
                dp[j][2] = Math.min(dp[j-1][0], dp[j-1][1]) + RGB[j][2];
                
                if (j == N-1) {
                    dp[j][i] = 987654321;
                }
            }
            
            for(int j = 0; j<3; j++) {
                MIN = Math.min(MIN, dp[N-1][j]);
            }
        }
        
        System.out.println(MIN);
    }
}