[알고리즘 PS] 백준 1149 RGB 거리 자바 문제 풀이

문제

해당 포스팅은 백준의 1149번 RGB 거리 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

해결법

문제를 해결하기 위해서 필요한 전처리를 해보자.

우선 이 문제는 입력이 n이라면 arr[n][3] 의 배열이 필요하다.

왜? n개의 집이 있을 때 각각이 갖는 RGB 색의 가중치가 다르기 때문에.

 

그래서 예제의 입력을 우리가 생각한 배열에 담으면 다음과 같다.

3
26 40 83
49 60 57
13 89 99

    26          40          83
house[0][0] house[0][1] house[0][2]

    49          60          57
house[1][0] house[1][1] house[1][2]

    13          89          99
house[2][0] house[2][1] house[2][2]

이제 전처리가 끝났다.

문제를 접근해보자.

 

접근법

 

이 문제의 핵심은 house[1][1]의 집은 절대로 house[0][1]의 집의 색과 같을 수 없다는 것이다.

한 집을 선택했을 때, 전 집의 색과 겹치지만 않는다면 2가지의 경우가 가능한 것이다.

그럼 모든 색을 칠할 수 있는 첫 번쨰 집을 제외하고 새롭게 house 배열을 update할 수 있다.

집의 수(i)와 색의 가중치(j : RGB 총 3이 된다) 가 담긴 i, j만큼 반복을 돌면서 현재 까지의 가중치 합이 최소인 잡과 현재 집의 가중치를 더하면 해당 집의 최소 가중치의 비용을 알 수 있지 않을까?

3
26 40 83
49 60 57
13 89 99

      26              40               83
  house[0][0]     house[0][1]     house[0][2]

49 + min(40, 83)  60 + min(26, 83)  57 + min(26, 40)
  house[1][0]      house[1][1]      house[1][2]

13 + min(house[1][1], house[1][2]) ...
  house[2][0]     house[2][1]     house[2][2]

그렇다.

 

정답이다.

 

그리고 마지막에 3가중치 합이 최소인 집을 선택하면 되는 것이다.

 

정답 코드

import java.io.*;
public class Main {

    static int[][] rgb;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        rgb = new int[n][3];
        for (int i = 0; i < n; i++) {
            String[] rgbs = br.readLine().split(" ");
            for (int j = 0; j < rgbs.length; j++) {
                rgb[i][j] = Integer.parseInt(rgbs[j]);
            }
        }
        bw.flush();
        bw.close();
    }
    private static int rgbWeight(int n, int m){
        if(n == 0) return myMinimum(rgb[0][0], rgb[0][1], rgb[0][2]);

        return myMinimum(rgb[n-1][0], rgb[n-1][1], rgb[n-1][2]);
    }

    private static int myMinimum(int a, int b, int c){
        return Math.min(a, Math.min(b, c));
    }
}

---

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.