[백준] RGB 거리 2 JAVA

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

17404번: RGB거리 2

 

1. 문제 이해 및 유형

dp(원형, circular)

 

RGB 거리에는 집이 N개 있는데, 각 집을 아래 규칙에 맞도록 칠한다.

- 1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다.

- N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다.

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

이 때, 집을 칠하는 최소 비용을 구하시오.

 

이전 집의 색이 R이라면 R을 제외한 색을 칠한 값과 같이 작은 문제들을 모아서 풀게되면 해결 할 수 있다고 생각하여

dp라고 생각하였다. 다만, 주어진 규칙에 따라야 하기 때문에 조금 고민이 되었다.

 

2. 문제 접근 방식

기본적으로 상태공간을 1~N까지의 집과, 각각의 상태(R,G,B)에 따라 

dp[N][3 (Color)] = N번째 집을 color로 칠했을 때 최소 비용 이라고 정한다.

결국, 마지막 집 N번집과 1번집만 해결하면 된다고 생각했다.

이러한 부분을 분리해서 생각하면

첫 번째 집이 R일 때 마지막집이 G 또는 B로 색칠되었을 때 최소값

첫 번째 집이 G일 때 마지막집이 R 또는 B로 색칠되었을 때 최소 값.

첫 번째 집이 B일 때 마지막집이 R 또는 G로 색칠 되었을 때 최소값.

이전에는 dp[마지막 집][color] 중 최소값을 찾기 때문에 첫 집이 무슨 색인지 모르지만 마지막집은 무슨 색으로 칠했을 때 가장 최소인지 알 수 있었다.

첫번째 집의 색을 우리가 정해준다. 정해주는 방법은 색칠할 값을 그대로 두고 나머지 값을 매우 큰 값으로 초기화하여

선택되지 못하게 하면 된다.

 

정리) 총 3번 돌거다. 

첫 번째 집 색깔에 따라 돌아보고 마지막 집에서 첫번째 집 색과 다른 색일 때 값을 구해본다.

/*
2022.01.13
문제번호 : Q17404
이름 및 난이도 : RGB거리 2 Gold IV
문제이해 
-----------------
N개의 집이 있고 거리는 선분으로 나타낼 수 있다. (1~N번집)
각각의 집이 RGB로 칠하는 비용이 주어질 때 아래 규칙을 만족하며 칠하는 최소 비용
- 1번 집은 2번과 N번 집의 색과 같지 않다.
- N번 집의 색은 N-1번 과 1번 집의 색과 같지 않다.
- i(2<=i<=N-1)번 집은 i-1, i+1번집과 같지 않다.

제한 조건 : 
접근 방법 :
 원형으로 이루어진 형태에서의 dp이다.
 주어진 조건에 따라 case를 나누어 계산한다.
 1번째 집이 R일 때 1~~~N-1  N번째 집은 G or B (dp[n-1][G] + B or dp[n-1][B] + G)
                                              dp[n-1][R] + Math.min(B,G);
 1번째 집이 G일 때 1~~~N-1 N번째 집은 R,B
   - n번째 집을 R로 칠할 때
    dp[n][R] = dp[n-1][G]+cost[n][R] or dp[n-1][B] + cost[n][R];
    dp[n][G] X
    - n번째 집을 B로 칠할때
    dp[n][B] = dp[n-1][G]+cost[n][B] dp[n-1][R]+cost[n][B]
*/

import java.io.*;
import java.util.*;
public class Main {
    static int N;
    static int cost[][];
    static int[][] dp;
    final static int RED =0;
    final static int BLUE =1;
    final static int GREEN =2;
    final static int INF = 10000000;
    public static void main(String[] args) throws IOException{
        input();
        solution();
    }
    public static void input() throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        cost = new int[N][3];
        StringTokenizer st;
        for(int i =0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            cost[i][RED] = Integer.parseInt(st.nextToken());
            cost[i][GREEN] = Integer.parseInt(st.nextToken());
            cost[i][BLUE] = Integer.parseInt(st.nextToken());
        }
    }
    public static void solution(){
        int ans = Integer.MAX_VALUE;
        for(int i =0;i<3;i++){
            dp = new int[N][3];
            Arrays.fill(dp[0],INF);
            dp[0][i] = cost[0][i];  // RED  GREEN BLUE
            //1~N-1번째 집 계산
            for(int j =1;j<N;j++){
                dp[j][RED] = Math.min(dp[j-1][BLUE], dp[j-1][GREEN]) + cost[j][RED];
                dp[j][BLUE] = Math.min(dp[j-1][RED], dp[j-1][GREEN]) + cost[j][BLUE];
                dp[j][GREEN] = Math.min(dp[j-1][RED], dp[j-1][BLUE]) + cost[j][GREEN];
                if(j==N-1)
                    dp[j][i] = INF;
            }
            int min = Math.min(dp[N-1][RED],Math.min(dp[N-1][GREEN],dp[N-1][BLUE]));
            if(min < ans)
                ans = min;
        }
        
        System.out.println(ans);
    }
}

 

3. 문제 추천 및 얻은점

이전에 프로그래머스에서 '도둑질'이라는 문제를 풀어보았다.

 https://programmers.co.kr/learn/courses/30/lessons/42897

코딩테스트 연습 - 도둑질

이 문제를 통해 dp에서 상태를 분리한 이후에 다시 상태를 제어할 수 있다는 것을 알았다.

특히 이 문제와 비슷하게 마지막과 처음 상태를 고려하여 생각하였을 때 풀 수 있다.

이러한 점을 주의하여 풀어보면 좋을 것 같다.