스노우보드 참 좋아하는데 맨날 키보드 앞에만 있네

백준 1149 : RGB거리 본문

개발/Algorithm

백준 1149 : RGB거리

워너-비 2018. 3. 10. 00:30

백준URL : 백준 1149 RGB거리


시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초128 MB192909284684048.432%

문제

RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이다. 처음 집과 마지막 집은 이웃이 아니다.

각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠할 때 드는 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로 칠할 때, 초록으로 칠할 때, 파랑으로 칠할 때 드는 비용이 주어진다.

출력

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

예제 입력 

3
26 40 83
49 60 57
13 89 99

예제 출력 

96

 



문제 분석


N과 N쌍의 R, G, B 비용이 주어진다.

N개의 집에 R, G, B 세 가지 색상을 이웃과 중복되지 않게 모든 집을 칠할 때, 소요되는 비용의 최소값을 출력하는 문제이다.


두 가지 풀이법이 있다.



방법 1. 모든 경우의 수를 구하여 최소값 찾기


총 N개의 집이 있다.

첫번째 집을 칠할 경우는 R, G, B 3가지

두번째 집은 첫번째 집과 다른 색으로 칠해야 하므로 R-G, R-B, G-R, G-B, B-R, B-G 6가지

세번째 집을 칠할 경우는 R-G-R, R-G-B, R-B-R, R-B-G ... B-G-B 12가지

...

N번째 집은 3 * 2^(N-1) 가지


따라서 N의 최대값이 1000이므로, 최대 3 * 2^999 의 경우를 탐색한 후 결과값 중 최소값을 출력해주면 된다.

효율적이지 못한 방법이지만, 소스코드를 작성해보니 의외로 시간초과가 발생하지 않아 정답으로 인정되었다.


int형 변수 N에 집의 갯수를 입력받고, int형 2차원 배열에 RGB 색상을 입력받는다.

현재 집의 번호, 직전의 집의 색상, 현재 총 비용. 이 세가지를 매개변수로 재귀함수를 작성했다.

첫번째 집을 시작으로 함수를 호출한다.

마지막 집을 호출되었을때, 총 비용이 최소값이면 저장한다.

모든 탐색이 끝나면, 최소값을 출력한다.


소스코드는 아래와 같다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.util.Scanner;
 
public class Main {
    
    static int color[][];
    static int n;
    static int result = Integer.MAX_VALUE;
    
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        
        n = s.nextInt();
        color = new int [n][3];
        
        for(int i = 0 ; i < n ; i++) {
            for(int j = 0 ; j < 3 ; j++) {
                color[i][j] = s.nextInt();
            }
        }
        
        for(int i = 0 ; i < 3 ; i++)
            search(0, i, 0);
        
        System.out.println(result);
    }
    
    static void search(int index, int rgb, int t) {
        
        int total = t;
        
        total += color[index][rgb];
            
        if(index == n-1) {
            result = Math.min(total, result);
            return;
        }
        else {
            for(int i = 0 ; i < 3 ; i++) {
                if(rgb != i)
                    search(index+1, i, total);
            }
        }
    }
}





방법 2. 다이나믹프로그래밍 (Dynamic Programming)


위와 같은 문제는 다이나믹프로그래밍을 이용한 해결이 더 효율적이다.

Bottom-up 방식으로 문제를 크기가 작은 문제부터 차례대로 풀면, 모든 경우의 수를 굳이 따져볼 필요가 없다.

N개의 집을 칠하는 최소값을 구하기 위해, 1개의 최소값, 2개, 3개.. N개 순으로 최소값을 차례대로 구한다.


Step 1. 입력

먼저 int형 변수 n에 집의 개수와 int형 배열 color[N][3]에 비용을 입력받는다.

최소비용은 2차원 배열 total_cost[N][3]에 저장해 나갈것이다.

// total_cost[집의 순서(0부터 N-1까지)][R=0, G=1, B=2]


Step 2. 최소비용 배열에 저장

집의 색상은 R, G, B 이므로 세가지 경우인 것에 유의한다.


- 첫번째 집은 누적된 비용이 없기 때문에 최초 금액을 그대로 입력한다.

total_cost[0][0= color[0][0]; // r
total_cost[0][1= color[0][1]; // g
total_cost[0][2= color[0][2]; // b


- 두번째부터는 현재 집을 R, G, B로 칠했을 경우의 최소값을 각각 구하여 배열에 입력한다.


i번째 집을 R로 칠한 경우 현재까지의 금액이 최소값은, i-1번째까지의 최소값에 i번째 R 비용을 더해주는 것과 같다.

i-1번은 G 혹은 B만 칠할 수 있으므로 둘 중 작은값을 찾으면 된다.

이후 G, B로 칠한경우도 동일하게 시행한다.

N-1까지 반복연산을 수행한다.

for(int i = 1; i < n ; i++) {
      total_cost[i][0= Math.min(total_cost[i-1][1], total_cost[i-1][2]) + color[i][0]; // r
      total_cost[i][1= Math.min(total_cost[i-1][0], total_cost[i-1][2]) + color[i][1]; // g
      total_cost[i][2= Math.min(total_cost[i-1][0], total_cost[i-1][1]) + color[i][2]; // b
}


- 마지막인 N-1번째에서 R, G, B인경우 중 최소값을 찾으면, 그게 전체의 최소값이 된다.


소스코드는 다음과 같다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        
        int n = s.nextInt();
        
        int total_cost[][] = new int[n][3];
        int color[][] = new int[n][3];
        
        for(int i = 0 ; i < n ; i++) {
            for(int j = 0 ; j < 3 ; j++) {
                color[i][j] = s.nextInt();
            }
        }
        
        total_cost[0][0= color[0][0];
        total_cost[0][1= color[0][1];
        total_cost[0][2= color[0][2];
        
        for(int i = 1; i < n ; i++) {
            total_cost[i][0= Math.min(total_cost[i-1][1], total_cost[i-1][2]) + color[i][0];
            total_cost[i][1= Math.min(total_cost[i-1][0], total_cost[i-1][2]) + color[i][1];
            total_cost[i][2= Math.min(total_cost[i-1][0], total_cost[i-1][1]) + color[i][2];
        }
        
        int result = Math.min(total_cost[n-1][0], Math.min(total_cost[n-1][1], total_cost[n-1][2]));
        
        System.out.println(result);
    }
}
 




방법 2는 전체의 경우를 따진 방법 1보다 시간이 절약되는 것을 확인할 수 있었다.

방법1(160MS) > 방법2(128MS)

Comments