[백준/DP] 17404 RGB거리2 - 자바

(옵시디언 기록일 : 23년 12월 30일)

 

문제

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

17404번: RGB거리 2

 

풀이

1번집과 N번집의 색깔이 같이 않게 하려면
- 1번집 R 일 경우 1번집 G, B를 DP값을 무한대로
- 1번집 G 일 경우 1번집 R, B를 DP값을 무한대로
- 1번집 B 일 경우 1번집 R, G를 DP값을 무한대로
설정하고 반복문을 3번 돌린다. 
여기서 첫번째 집에서 선택한 색깔 이외에 다른 색깔을 첫집에서 사용할 수 없으므로 무한대로 초기화를 해 놓는다. 

두번째집부터 색칠을 하게 되면 마지막 집에서는 첫번째 집에서 선택한 색깔을 칠할 수 없으므로 `dp[마지막집][첫번째 집의 색깔]` 을 고려하지 않는다. 

 

import java.util.*;  
import java.io.*;  
  
public class BOJ_17404_G4_RGB거리2 {  
    static StringTokenizer st;  
    public static void main(String[] args) throws Exception {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        int n = Integer.parseInt(br.readLine());  
        int[][] arr = new int[n+1][4];  
        int[][] dp = new int[n+1][4];  
  
        for (int i = 1; i <= n; i++) {  
            st = new StringTokenizer(br.readLine());  
            arr[i][1] = Integer.parseInt(st.nextToken());  
            arr[i][2] = Integer.parseInt(st.nextToken());  
            arr[i][3] = Integer.parseInt(st.nextToken());  
        }  
  
        int min = Integer.MAX_VALUE;  
  
        // R, G, B 각각 시작  
        for(int c = 1; c <= 3; c++) {  
            for (int i = 1; i <= 3; i++) {  
                if(c == i) dp[1][i] = arr[1][i];  
                else dp[1][i] = 1000 * 1000;  
            }  
  
            for (int i = 2; i <= n; i++) {  
                dp[i][1] = arr[i][1] + Math.min(dp[i-1][2] , dp[i-1][3]);  
                dp[i][2] = arr[i][2] + Math.min(dp[i-1][1] , dp[i-1][3]);  
                dp[i][3] = arr[i][3] + Math.min(dp[i-1][1] , dp[i-1][2]);  
            }  
  
            for (int i = 1; i <= 3; i++) {  
                if(c != i) min = Math.min(min, dp[n][i]);  
            }  
        }  
  
        System.out.println(min);  
  
    }  
}