[백준][boj] RGB거리 2(17404) - JAVA

문제 파악

가장 중요한 조건은

1. i번째 집은 i-1번째 집과 i+1번째 집과 색이 같지 않아야 한다.
2. 첫 번째 집과 마지막 집은 색이 같지 않아야 한다.

두 조건이였습니다.

 

문제 풀이

 

• 첫 번째 집의 색상을 R, G, B 중 하나로 고정해서 3가지 경우를 각각 계산
• DP 배열을 사용하여 i번째 집을 어떤 색으로 칠했을 때의 최소 누적 비용을 저장
  -> DP 배열은 매번 새로 선언해야 함. 
• 마지막 집의 색상이 첫 번째 집과 다른 경우만 정답 후보 ! 

 

 

코드 구현

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

class Main {
    static int n;
    static int [][] cost;
    static final int INF = 1_000_000_000;
    static int answer = INF;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        StringTokenizer st;

        cost = new int[n][3];

        for(int i=0; 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());
        }

        for(int firstColor = 0; firstColor < 3; firstColor ++){
            int [][] dp = new int[n][3];

			// 배열에 첫번 째 집에서 선택한 색깔만 저장
            for(int i = 0; i < 3; i ++){
                if( i == firstColor ){
                    dp[0][i] = cost[0][i];
                }else{
                    dp[0][i] = INF;
                }
            }
            
            
            // 점화식 - dp[i][j] = i번째 집을 j색으로 칠했을 때의 최소 누적 비용 
            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];
            }

			// 마지막 색상과 첫번째 색상이 같다면 조건에서 배제
            for(int lastColor = 0; lastColor < 3; lastColor ++){
                if(lastColor == firstColor) continue;
                answer = Math.min(answer, dp[n-1][lastColor]);
            }
        }

        System.out.println(answer);
    }
}

 

 

Review 

점화식 세우는 법 연습 필요 😂