[java] 백준 알고리즘 1149번 RGB거리 풀이

이중배열로 문제를 풀어야할 거라고는 생각 못했다.

이중배열로 문제를 풀어야하는 경우가 이번이 처음이어서

다른 사람의 소스를 참고하면서 만들었다.

문제를 착각하면 안되는 것이

빨강->파랑->빨강, 파랑->초록->파랑 처럼 양 옆의 이웃하고만 색이 다르면 된다. 

동시에 연속된 세 집이 다른 색이어야한다는 게 아니다. 

(알고리즘은 문제를 제대로 이해하는게 중요한 듯 싶다.)

풀이방법:

이중배열을 통해 각 행을 '집'으로 간주하고 3열을 '페인트 색'으로 간주한다.

0행(첫번째 집)	(0,0) 빨강	(0,1) 초록	(0,2) 파랑
1행(두번째 집)	(1,0) 빨강	(1,1) 초록	(1,2) 파랑
2행(세번째 집)	(2,0) 빨강	(2,1) 초록	(2,2) 파랑
3행(네번째 집)	(3,0) 빨강	(3,1) 초록	(3,2) 파랑

마지막 집에 선택할 색깔과 한 칸 전의 집은 다른 2가지 색을 골라야 조건이 성립한다.

마지막 집이 빨강이라면 한 칸 전의 초록 혹은 파랑색 집을 칠하는데 최소 비용을 사용한 방법을 골라야한다.

마지막 집이 초록이라면 한 칸 전의 빨강 혹은 파랑색 집을 칠하는데 최소 비용을 사용한 방법을 골라야한다.

그러면 마지막 집에 빨강색으로 칠했을 때 총 비용의 최솟값, 초록색으로 칠했을 때 총 비용의 최솟값, 

파랑색으로 칠했을 때 총 비용의 최솟값 중 가장 저렴한 방법을 선택하면 모든 방법의 최솟값을 구할 수 있다.

*소스

public class Baekjoon1149 {
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] colorCost = new int[1000][3]; // 각각의 집에 대한 페인트 비용
        int[][] sumColorCost = new int[1000][3]; // 모든 집에 대한 페인트 비용 최솟값
        
        for(int i=0; i<n; i++) { // 각각의 집에 대한 페인트 비용을 입력.
            String[] preInputArray = br.readLine().split(" ");
            int[] inputArray = new int[3];
            for(int j=0; j<preInputArray.length; j++) {
                inputArray[j] = Integer.parseInt(preInputArray[j]);
            }
            colorCost[i][0] = inputArray[0]; // 빨간 페인트 비용
            colorCost[i][1] = inputArray[1]; // 초록 페인트 비용
            colorCost[i][2] = inputArray[2]; // 파랑 페인트 비용
        }
        
        /* 초기값 설정 */
        sumColorCost[0][0] = colorCost[0][0]; 
        sumColorCost[0][1] = colorCost[0][1];
        sumColorCost[0][2] = colorCost[0][2];
        
        for(int j=1; j<n; j++) {
            sumColorCost[j][0] = Math.min(sumColorCost[j-1][1], sumColorCost[j-1][2]) + colorCost[j][0]; // 마지막 집을 빨간색으로 했을 때 최솟값(앞에는 초록 혹은 파랑 집의 총 최소비용)
            sumColorCost[j][1] = Math.min(sumColorCost[j-1][0], sumColorCost[j-1][2]) + colorCost[j][1]; // 마지막 집을 초록색으로 했을 때 최솟값(앞에는 빨강 혹은 파랑 집의 총 최소비용)
            sumColorCost[j][2] = Math.min(sumColorCost[j-1][0], sumColorCost[j-1][1]) + colorCost[j][2]; // 마지막 집을 파란색으로 했을 때 최솟값(앞에는 빨강 혹은  집의 총 최소비용)
        }
        
        int minColorCost = Math.min(sumColorCost[n-1][0], Math.min(sumColorCost[n-1][1], sumColorCost[n-1][2])); // 총 세가지 페인트 중 가장 저렴한 최솟값으로 출력.
        System.out.println(minColorCost);
    }
 
}