백준 1149번 : RGB거리 java

이 문제는 이전의 row와 다음의 row를 비교하여 같은 column에 수들이 들어있지 않게 더하여 최솟값이
나오게 하는 문제입니다.

저는 이 문제를 아래로 내려가면서 각 항의 합이 최솟값이 되는 조건을 찾아서 더해가며 풀었습니다.

 

 

왼쪽의 그림은 예제 1번의 입력값입니다.

이 그림을 통해서 어떤 규칙으로 문제를 푸는지
보여드리겠습니다.

 

 

 

이미 지나간 row는 파란색으로 표시하였고 지나가지 않은
row는 검은색으로 표시하였습니다.

이제 다음 row의 항들의 중에서 합이 최솟값이 되기 위해서는 어떤 항을 더해야하는지를 알아보겠습니다.

 

 

 

이 그림에서 빨간 항에서의 조건에 따른 최솟값을 구하기 위해서는 빨간 항이 있는 row의 위의 row에서 column이 다를 때의 최솟값을 더해야 합니다.

더할 수 있는 항들을 주황색으로 표시하였습니다.

 

 

 

더할 수 있는 최솟값인 40을 더해서 89로 만들고 다음 항들도 똑같이 구해줍니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

이렇게 완성되었을 때 가장 아래의 row 중 가장 작은 수가 답입니다.

이제 코드를 보여드리도록 하겠습니다.

---

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

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

        int N = Integer.parseInt(br.readLine());
        int[][] rgbArr = new int[N][3];

        for(int i = 0; i<N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            for(int j = 0; j<3; j++)
                rgbArr[i][j] = Integer.parseInt(st.nextToken());
        }

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

        int min = Math.min(Math.min(rgbArr[N-1][0], rgbArr[N-1][1]), rgbArr[N-1][2]);

        System.out.println(min);
    }
}

위에 보여드린 것과 같은 구조로 문제를 해결하였습니다.