[백준] 1149번 : RGB거리

1149번: RGB거리

# 문제

 

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

# 입력

 

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

 

# 출력

 

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

 

# 예시 입력

3
26 40 83
49 60 57
13 89 99

# 예시 출력

96

---

 

동적 프로그래밍으로 해결해야 하는 문제이다. DP로 풀어야 한다는 것을 인지했으나, 길을 잘못 들어서 Greedy 방식으로 문제를 접근하게 되어 다시 설계하는 불상사가 발생했다. 몇 가지 예를 입력해보고 다 맞는 것 같은데 왜 틀렸다고 채점되는거지...? 하다가 반례를 하나 보게 되었다.

3
1 9 1
3 1 2
9 1 9

라는 입력이 주어졌을 때 올바르게 접근했다면 정답은 4가 될 것이다. Red - Blue - Green순으로 집을 색칠하는 것이다. 하지만 처음 코딩했던 Greedy로 푼다면 11이 나올 것이다. 각 행에서 가장 작은 값을 찾아나서므로 Red or Blue - Green - Red or Blue순으로 색칠하게 된다. 프로그램에서든 웹에서든 다양한 테스트 예제는 정말 중요하다고 느낀다.

 

먼저 이차원 배열 2개가 필요하다. 하나는 처음 각 집을 색깔 별로 칠할 때 드는 비용을 저장할 RGB 배열

 

* RGB[n][0] = Red로 칠하는데 드는 비용

* RGB[n][1] = Green으로 칠하는데 드는 비용

* RGB[n][2] = Blue로 칠하는데 드는 비용

 

나머지 하나는, 갖을 수 있는 최소값을 누적해 나가며 저장할 배열이다.

 

입력된 배열

1	9	1
3	1	2
9	1	9

1)

1	9	1
(3+9) || (3+1)	(1+1) || (1+1)	(2+1) || (2+9)
?	?	?

2)

1	9	1
4	2	3
(9+2) || (9+3)	(1+4) || (1+3)	(9+4) || (9+2)

3)

1	9	1
4	2	3
11	4	11

3) 표의 맨 아래줄을 보면 11, 4, 11이 최종 값으로 저장되었다. 문제에서 원하는 답은 이 3개 중 가장 작은 수 이므로 4가 답이 될 수 있다.

 

static int getMin(int n) {

        int min;
        int[][] arr = new int[n+1][3];

        arr[1][R] = RGB[1][R]; arr[1][G] = RGB[1][G]; arr[1][B] = RGB[1][B];

        for(int i=2; i<=n; i++)
            for(int j=0; j<3; j++) //Color Iterator
                arr[i][j] = Math.min(RGB[i][j] + arr[i-1][(j+1)%3], RGB[i][j] + arr[i-1][(j+2)%3]);

        min = Math.min(arr[n][R], arr[n][G]);
        min = Math.min(min, arr[n][B]);

        return min;
    }

이해하기 힘든 코드는 아마 arr[i][j] = Math.min(RGB[i][j] + arr[i-1][(j+1)%3], RGB[i][j] + arr[i-1][(j+2)%3]); 라고 생각된다.

for(int j=0; j<3; j++)루프는 RGB 컬러를 순회하는 의미를 갖는다. R=0 G=1 B=2 이므로.

 

Math.min(a, b)는 a, b중에 더 작은 값을 반환 받는 것 이다.

RGB[i][j] + arr[i-1][(j+1)%3]에서

RGB[i][j] : N번째 집에 색을 칠할 때 드는 비용(RGB[i][0] = Red, RGB[i][1] = Green, RGB[i][2] = Blue Cost)

arr[i-1][(j+1) % 3] : j는 0~2이므로 (j+1) % 3을 하게되면 현재 j와는 무조건 다른 값을 가지게 된다. 이는 문제에 제시된 조건 i번 째 집은 i-1번째, i+1번째 집과 다른 색을 가져야 한다. 라는 조건을 충족시킨다.

 

# Whole Code </>

import java.util.Scanner;

public class Main {

    static final int R = 0;
    static final int G = 1;
    static final int B = 2;
    static final int MAX = 1001;
    static int[][] RGB = new int[MAX][3];

    static boolean isPossible(int i){

        boolean flag = true;
        if(RGB[i][R] < 1 || RGB[i][R] > 1000) flag = false;
        if(RGB[i][G] < 1 || RGB[i][G] > 1000) flag = false;
        if(RGB[i][B] < 1 || RGB[i][B] > 1000) flag = false;

        return flag;
    }

    static int getMin(int n) {

        int min;
        int[][] arr = new int[n+1][3];

        arr[1][R] = RGB[1][R]; arr[1][G] = RGB[1][G]; arr[1][B] = RGB[1][B];

        for(int i=2; i<=n; i++)
            for(int j=0; j<3; j++) //Color Iterator
                arr[i][j] = Math.min(RGB[i][j] + arr[i-1][(j+1)%3], RGB[i][j] + arr[i-1][(j+2)%3]);

        min = Math.min(arr[n][R], arr[n][G]);
        min = Math.min(min, arr[n][B]);

        return min;
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        if(n < 2 || n > 1000) System.exit(0);

        for(int i=1; i<=n; i++){
            RGB[i][0] = sc.nextInt();
            RGB[i][1] = sc.nextInt();
            RGB[i][2] = sc.nextInt();
            if(!isPossible(i)) System.exit(0);
        }
        System.out.printf("%d\n", getMin(n));
    }
}