[BOJ 백준] 1149번 - RGB거리 (Java)

문제 출처 : www.acmicpc.net/problem/1149

1149번: RGB거리

두번째 줄부터 공백으로 구분되는 빨강, 초록, 파랑 집의 색칠 비용이 주어질때,

규칙에 부합하면서 최소의 비용을 계산하는 문제가 있다.

 

규칙

예를 들어 N이 4일경우

1번째 집은 2번째 집의 색과 같으면 안된다.

2번째 집은 1번째 집과 3번째 집의 색과 같으면 안된다.

3번째 집은 2번째 집과 4번째 집의 색과 같으면 안된다.

4번째 집은 3번째 집의 색과 같으면 안된다.

 

이때 1번째 집과 3번째 집의 색은 같을 수도 있다.

이때 2번째 집과 4번째 집의 색은 같을 수도 있다.

 

 

접근

1. 입력으로 주어지는 비용을 저장할 2차원 배열과, 각 집의 누적 최소 비용합을 저장할 2차원 배열을

생성한다.  

2. 첫번째 집의 색칠비용의 값을 첫번째 집의 누적 최소 비용합 배열에 동시 저장한다.

3. 이후 나머지 집들의 색칠비용을 비용을 저장할 배열에 저장한다.

4. 반복문을 통해 두번째 집부터 직전 집에 색칠한 색을 제외한 나머지 색 중에서 최소비용을 현재 집의 색깔 비용을

합하여 누적 최소 비용합 배열에 저장한다.

5. 가장 마지막 집의 누적 비용합 배열중에서 가장 적은 값이 정답이 된다.

 

예시 (예제 활용)

세곳의 집에서 색칠을 한다고 하고 각 집의 색칠 비용이 다음과 같을때 입력이 다음과같다.

3

26 40 83

49 60 57

13 89 99

 

위 입력 값을 좌표로 지정한다면 다음과 같이 지정할 수 있다.

(0,0) (0,1) (0,2)

(1,0) (1,1) (1,2)

(2,0) (2,1) (2,2)

 

이때 두번째 집에서 빨강색(1,0)을 칠하려면 첫번째 집에서 초록(0,1) 또는 파랑(0,2)을 선택해야한다.

두번째 집에서 빨강색을 선택할때 최소 누적합은 두번째 집 빨강의 색칠비용 49 + 첫번째집의 초록, 파랑 비용중 낮은 값이 된다. 즉, 두번째 집에서 빨강색을 칠할때 최소 누적합은 40(첫번째집에서 초록) + 49(두번째 집에서 빨강) = 89가 된다.

 

두번째 집에서 초록색(1,1)을 칠하려면 첫번째 집에서 빨강(0,0) 또는 파랑(0,2)을 선택해야한다.

두번째 집에서 초록색을 선택할때 최소 누적합은 두번째 집 초록의 색칠비용 60 + 첫번째집의 빨강, 파랑 비용중 낮은 값이 된다. 즉, 두번째 집에서 초록색을 칠할때 최소 누적합은 26(첫번째집에서 파랑) + 60(두번째 집에서 초록) = 86이 된다.

 

작성 코드

import java.io.*;

public class Main {
    static int[][] ground;
    static int[][] sum;

    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 size = Integer.parseInt(br.readLine());
        ground = new int[size][3];
        sum = new int[size][3];

        for(int i=0; i<size; i++){
            String[] input = br.readLine().split(" ");
            for(int j=0; j<ground[0].length; j++){
                ground[i][j] = Integer.parseInt(input[j]);
                if(i == 0){
                    sum[0][0] = ground[0][0];
                    sum[0][1] = ground[0][1];
                    sum[0][2] = ground[0][2];
                }
            }
        }
        br.close();

        for(int i=1; i<size; i++){
            sum[i][0] = Math.min(sum[i-1][1],sum[i-1][2]) + ground[i][0];
            sum[i][1] = Math.min(sum[i-1][0],sum[i-1][2]) + ground[i][1];
            sum[i][2] = Math.min(sum[i-1][0],sum[i-1][1]) + ground[i][2];
            if(i == size-1){
                int min = Math.min(sum[i][0],Math.min(sum[i][1],sum[i][2]));
                bw.write(min+"");
                bw.close();
            }
        }
    }
}

 

다른 코드들 확인

github.com/devdinist/BOJ_Code

devdinist/BOJ_Code