[백준] 17404번 RGB거리 2 풀어보기 [Java]

모든 집을 가장 적은 비용으로 색칠하는 문제이다.

조건으로는

• 현재 집에서 바로 전 집과 다음 집에는 다른 색을 칠해야 된다.
• 처음과 끝 집은 이어져 있다.

 

👨‍🏫 풀이

DP문제이다. 처음 집과 마지막 집을 제외하고는 이전 집의 색깔만 다르게 칠하면 조건을 만족할 수 있다.

 

1. 집을 색칠하기 시작할 때, 처음 집의 색깔을 정해놓고 칠한다.

2. 지금 칠하는 색과 다른 색으로 칠한 앞에 집의 값중에서 작은 것을 선택한다.

 

 

첫번째 집은 항상 미리 선택을 해놓기 때문에, 두번째 집만 첫번째 집의 색을 선택한 값으로 설정을 해놓는다. 첫번째 집과 동일한 색을 칠하는 경우는 MAX_VALUE로 설정을 해준다.

 

return 값은 첫번째 집과 마지막 집이 같으면 안되기 때문에, 다른 색으로 칠해진 값중 작은 값을 return 해준다.

 

👨🏻‍💻코드

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

public class Main {
    static int N;
    static int[][] cache, cost;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        cost = new int[N][3];
        cache = new int[N][3];
        for(int i = 0 ; i < N ; i++){
            cost[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(n -> Integer.parseInt(n)).toArray();
        }

        int ans = Integer.MAX_VALUE;
        ans = Math.min(ans, dp(0));
        ans = Math.min(ans, dp(1));
        ans = Math.min(ans, dp(2));

        System.out.println(ans);
    }
    static int dp(int s){
        cache[0][0] = cost[0][0];
        cache[0][1] = cost[0][1];
        cache[0][2] = cost[0][2];

        int notS1 = (s+1) % 3;
        int notS2 = (s+2) % 3;

        //다음꺼는 s를 선택하면 안됨
        cache[1][s] = Integer.MAX_VALUE;
        cache[1][notS1] = cache[0][s] + cost[1][notS1];
        cache[1][notS2] = cache[0][s] + cost[1][notS2];

        for(int i = 2 ; i < N ; i++){
            cache[i][0] = Math.min(cache[i-1][1], cache[i-1][2]) + cost[i][0];
            cache[i][1] = Math.min(cache[i-1][0], cache[i-1][2]) + cost[i][1];
            cache[i][2] = Math.min(cache[i-1][0], cache[i-1][1]) + cost[i][2];

        }

        return Math.min(cache[N-1][notS1], cache[N-1][notS2]);
    }

}