RGB거리 2 17404 Java

 

17404번: RGB거리 2

package 백준.자바.RGB거리2_17404;

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

public class Main {
    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] RGB = new int[N][3];
        int[][] d = new int[N][3];

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

        int total = Integer.MAX_VALUE;
        
        // R, G, B 각각에 대해 한 번씩 반복
        for(int i =0 ; i < 3; i++){
            // i == 0인 경우, R 이외의 G, B는 각각 최댓값 + 1로 초기화
            for(int k = 0; k < 3; k++){
                if(i == k) d[0][k] = RGB[0][k];
                else d[0][k] = 1001;
            }

            // dp 
            for(int j = 1; j < N; j++){
                d[j][0] = Math.min(d[j-1][1], d[j-1][2])+RGB[j][0];
                d[j][1] = Math.min(d[j-1][0], d[j-1][2])+RGB[j][1];
                d[j][2] = Math.min(d[j-1][0], d[j-1][1])+RGB[j][2];
            }

            // 처음 고정 시켜놓은 값의 인덱스는 참조가 불가능하므로 
            // 해당 인덱스를 제외한 다른 인덱스의 최소값 결정
            int t = Integer.MAX_VALUE;
            for(int k = 0; k < 3; k++){
                if(i==k) continue;
                if(t > d[N-1][k]) t = d[N-1][k];
            }
            
            // 총 3번의 반복(R, G, B) 중 최소값을 갱신
            total = Math.min(t, total);
        }

        System.out.println(total);


    }


    public static void main(String[] args) throws Exception{
        new Main().solution();
    }
}

 

RGB1 문제와 다르게, RGB2는 시작점과 끝점이 이어져 있는 원 형태이다.

 

즉, 맨 처음 R을 선택했다면, N번째 선택에서는 R을 선택할 수 없으므로 G, B 중 하나를 골라야만 한다.

 

그러나 일반적인 dp 방식으로는 R, G, B 값을 각각 초기화하고, 셋 중 가장 나은 선택을 하므로

dp의 마지막 선택에서 해당 최소값이 R, G, B중 어디서 비롯된지 알 수 없다.

 

갱신된 값이 온전히 R로부터 비롯되도록 R을 선택한 경우, R을 제외한 G, B는 최댓값+1을 넣어 G, B의 선택의 의미가 없도록하고,

마지막 선택에서 R을 제외한 G, B에 올 수 있는 최소값을 선택하면

R에서 시작한 가능한 가장 작은 수를 얻을 수 있다.

 

같은 방식으로 G, B에도 적용하고, 3번의 루프에서 가장 작은 값을 출력하면 된다.

 

처음에는 3차원으로 구현할까 해보았지만, 기존에 갱신된 DP 배열을 재참조 하지 않기때문에

굳이 3차원으로 구현할 필요는 없어보여 2차원으로 구현했다.