[JAVA] 백준 17404번- RGB거리2

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

17404번: RGB거리 2

 

 

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

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        final int INF = 1000 * 1000 + 1;

        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n+1][3];
        int[][] dp = new int[n+1][3]; // i번째 집을 j 색상으로 칠하는데 최소 비용

        for(int i=1; i<=n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<3; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int min = INF;

        // 1번집이 각각 R, G, B로 선택 되었을때를 각각 따로 구함
        for(int i=0; i<3; i++){
            for(int j=0; j<3; j++){
                // 시작하는 집이 i 색깔로 선택되었을 때로 고정
                if(i==j) dp[1][j] = arr[1][j]; // 1번집을 i 색깔로 칠해 놓음
                else dp[1][j] = INF; // 다른 색은 선택되지 못하도록 비용을 최댓값으로 초기화
            }

            // n번 집의 색은 n-1번 집의 색과 같지 않아야 함
            for(int j=2; j<=n; j++){
                dp[j][0] = Math.min(dp[j-1][1], dp[j-1][2]) + arr[j][0];
                dp[j][1] = Math.min(dp[j-1][0], dp[j-1][2]) + arr[j][1];
                dp[j][2] = Math.min(dp[j-1][0], dp[j-1][1]) + arr[j][2];
            }
            for(int j=0; j<3; j++){
                if(i!=j && min > dp[n][j]){ // n번째 집을 칠할 때 시작 색깔을 제외한 색깔의 비용 중 가장 작은 비용 선택
                    min = dp[n][j];
                }
            }
        }
        System.out.println(min);
    }
}

 

https://yeoncoding.tistory.com/616

[JAVA] 백준 1149번- RGB거리

 

 

이전 RGB 거리 문제에서 1번째 집과 N번째 집의 색깔이 같지 않아야 한다는 조건이 추가되었다. 이전 문제랑 비슷하게 진행하면 쉽게 풀 수 있을 줄 알았는데 어려웠다.

 

 

이전 문제에서는 N번째 집이 R,G,B 일때로 나눠 각각 따졌었다.

 

이번에는 N번 집의 색과 1번 집의 색이 같으면 안되므로 N번 집의 색을 알려면 1번 집의 색도 알고 있어야 한다.

그러므로 1번 집이 각각 R,G,B로 선택 되었을 때를 따지고, N번 집을 칠할 때 1번 집과 다른 색깔의 것들만을 따지면 된다. 

즉, 반복문을 3번 돌려 1번집이 각각 R, G, B로 선택되었을때를 따로 구한다.

 

 

 

1번 집의 색을 고정시키고, 다른 색은 선택되면 안되게 해야한다.
예를 들어 1번 집의 색을 R로 정해 놓는다면 G와 B는 절대 선택되지 못하도록 1번 집의 G와 B의 비용을 최댓값으로 초기화시켜 놓는 것이다.

 

그 후 이전 RGB 거리 문제의 점화식과 마찬가지로 n번째 집의 색은 n-1집의 색과 같지 않도록 하는 최소비용을 채워나간다.

 

그리고 마지막으로 n번째 집을 R,G,B로 칠할 때의 경우의 비용들을 다 따지는 것이 아니라,

고정시킨 1번째 집과 다른 색깔의 집들 중에서의 최소비용을 구한다.