[백준 - 1149] RGB 거리 - Java

문제 설명

 

1149번: RGB거리

 

풀이 : Success

소스 코드

import java.util.Arrays;
import java.util.Scanner;

class Main {

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] rgbHouse = new int[n][3];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                rgbHouse[i][j] = sc.nextInt();
            }
        }

        for (int i = 0; i < n - 1; i++) {
            int[] minValueAndIndex = getMinValueAndIndex(rgbHouse[i]);
            for (int j = 0; j < 3; j++) {
                if (minValueAndIndex[1] != j) {
                    rgbHouse[i + 1][j] += minValueAndIndex[0];
                }
                else {
                    Arrays.sort(rgbHouse[i]);
                    rgbHouse[i + 1][j] += rgbHouse[i][1];
                }
            }
        }

        System.out.println(getMinValueAndIndex(rgbHouse[n-1])[0]);
    }

    public static int[] getMinValueAndIndex(int[] arr) {
        int minValue = arr[0], index = 0;
        for (int i = 1; i < arr.length; i++) {
            if (minValue > arr[i]) {
                minValue = arr[i];
                index = i;
            }
        }

        return new int[]{minValue, index};
    }
}

 

풀이 회고

문제에서 요구하는 것은 N개의 집이 주어질 때 한 집당 R G B 중 한 가지 색으로 색칠을 할 때에 최소한의 비용입니다. 이때 중요한 점은 현재 색칠하는 집의 색과 이전 집에 색칠된 색과 동일해서는 안된다는 점입니다.

 

이를 위해 저는 한 집에 색칠할 수 있는 색(R, G, B) 중 가장 적은 비용의 색을 선택하도록 했고 이 색을 다음 집에 R G B 색칠 비용에 누적 합산시켜주도록 했는데, 중복되면 안되므로 해당 색은 제외시켜 합산시켜주었습니다. 이를 코드로 나타내면 다음과 같습니다.

        for (int i = 0; i < n - 1; i++) {
            int[] minValueAndIndex = getMinValueAndIndex(rgbHouse[i]);
            for (int j = 0; j < 3; j++) {
                if (minValueAndIndex[1] != j) {
                    rgbHouse[i + 1][j] += minValueAndIndex[0];
                }
                else {
                    Arrays.sort(rgbHouse[i]);
                    rgbHouse[i + 1][j] += rgbHouse[i][1];
                }
            }
        }
        
        ...
        
    public static int[] getMinValueAndIndex(int[] arr) {
        int minValue = arr[0], index = 0;
        for (int i = 1; i < arr.length; i++) {
            if (minValue > arr[i]) {
                minValue = arr[i];
                index = i;
            }
        }

        return new int[]{minValue, index};
    }

 

위 코드를 보면 getMinValueAndIndex 메서드에서는 R G B 중 최소 비용값과 해당 인덱스(0~2)를 정수형 배열로 반환시켜주도록 했습니다. 이때 최소 비용값은 다음 집 R, G, B 색칠 비용에 누적시키기 위함이며, 해당 인덱스 값은 색의 중복 방지를 하기 위함이었습니다.

 

최종적으로 마지막 집에서의 R, G, B 색칠 비용은 처음 집부터 누적하여 합산해준 결과이므로 이 중에서의 최소값은 전체 집을 최소 비용으로 칠할 수 있는 경우에 해당합니다.

 

 

 

리팩토링

소스 코드

import java.util.Scanner;

class Main {

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] rgbHouse = new int[n][3];

        for (int j = 0; j < 3; j++) {
            rgbHouse[0][j] = sc.nextInt();
        }

        for (int i = 1; i < n; i++) {
            int pR = rgbHouse[i - 1][0], pG = rgbHouse[i - 1][1], pB = rgbHouse[i - 1][2];

            for (int j = 0; j < 3; j++) {
                rgbHouse[i][j] = sc.nextInt();
            }

            rgbHouse[i][0] += Math.min(pG, pB);
            rgbHouse[i][1] += Math.min(pR, pB);
            rgbHouse[i][2] += Math.min(pR, pG);
        }

        System.out.println(getMinValueAndIndex(rgbHouse[n - 1]));
    }

    public static int getMinValueAndIndex(int[] arr) {
        int minValue = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (minValue > arr[i]) {
                minValue = arr[i];
            }
        }

        return minValue;
    }
}

 

풀이 회고

앞서 구한 풀이의 경우 최소 비용과 인덱스를 이용하는 등 논리적으로 다소 번잡한 느낌이 있어 좀 더 유연하게 수정하고자 했습니다.

 

우선 현재 집에 색칠 비용값들에 이전 색칠 비용의 최소값을 누적 합산해주는 논리는 같지만 이번에는 중복 방지를 위해 인덱스를 사용하지 않고 현재 집에 대한 R 색칠 비용에 이전 집에 대한 G와 B 색칠 비용 중 최소값을 합산해주었고, 현재 집에 대한 G 색칠 비용에 이전 집에 대한 R와 B 색칠 비용 중 최소값을 합산하는 방식 등으로 구현했습니다. 이를 코드로 나타내면 다음과 같습니다.

 

        for (int i = 1; i < n; i++) {
            int pR = rgbHouse[i - 1][0], pG = rgbHouse[i - 1][1], pB = rgbHouse[i - 1][2];

            for (int j = 0; j < 3; j++) {
                rgbHouse[i][j] = sc.nextInt();
            }

            rgbHouse[i][0] += Math.min(pG, pB);
            rgbHouse[i][1] += Math.min(pR, pB);
            rgbHouse[i][2] += Math.min(pR, pG);
        }

 

최종적으로 마지막 집에 대한 색칠 비용은 각각의 경우별로 최소 값들로 합쳐진 것이므로 이 중에서 최소값을 구하면 원하는 결과를 도출할 수 있었습니다.

 

 

참고자료

• https://www.acmicpc.net/problem/1149