[BOJ] 1149 - RGB거리

-개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제 설명

www.acmicpc.net/problem/1149

1149번: RGB거리

난이도: 실버 1

사용 언어: JAVA

 

N개의 집이 일렬로 쭉 세워져 있는 RGB거리가 있습니다. 각각의 집을 빨강, 초록, 파란색 중 하나를 선택해서 칠해야 하며, 각각의 색깔로 칠하는데 드는 비용은 모두 다르며, 비용은 입력으로 주어집니다.

 

그리고 규칙이 하나 존재하는데, 바로 모든 집은 앞, 그리고 뒤의 집과 색깔이 같으면 안 된다는 것입니다. 가장 앞에 있는 첫 번째 집은 두 번째 집과 색이 같으면 안 되고, 네 번째 집은 세 번째, 그리고 다섯 번째 집과는 색깔이 같으면 안 됩니다. 즉 연속된 집을 같은 색깔로 두 번 이상 칠할 수 없습니다.

 

이때, 마지막 집까지 색을 칠했을 때 드는 최소 비용을 구하는 문제입니다.

 

풀이

이 문제는 다이나믹 프로그래밍을 이용해 해결할 수 있습니다. 저는 arr와 cost라는 두 개의 이차원 배열을 이용했습니다. arr배열은 입력 값을 저장시켜두는 용도로, 그리고 cost 배열은 다이나믹 프로그래밍을 위한 결괏값을 저장하는 용도로 사용했습니다. 

 

백준에서 제시한 예제를 가지고 설명을 해보겠습니다. 

 

3

26 40 83

49 60 57

13 89 99

 

첫 번째 집은 빨강으로 칠할 때는 26, 초록으로 칠할 때는 40, 파랑으로 칠할 때는 83의 비용이 든다는 것을 의미합니다. 두 번째, 세 번째 집도 같은 맥락으로 이해할 수 있습니다. 여기서 당연히 첫 번째 집만 색칠을 하는 경우에는 누적된 비용도 26 40 83일 것입니다. 이 값들을 cost 배열에 추가시켜 줍니다.

 

두 번째 집을 칠 할 때는, 첫 번째 집의 색을 고려해야 합니다. 즉, 두 번째 집을 빨강으로 칠하려면, 첫 번째 집은 초록, 또는 파랑으로 칠했어야 하고, 파랑으로 칠하려면, 첫 번째 집이 빨강 혹은 초록으로 칠해졌어야 합니다. 

 

위의 그림은 cost 배열 내에서 배열을 채워나가는 과정의 일부입니다. cost 배열의 첫 칸은 빨강, 두 번째 칸은 초록, 세 번째 칸은 파랑을 의미합니다. 이때 두 번째 집을 빨간색으로 칠 할 때의 누적 비용은, 첫 번째 집이 초록을 칠했을 때의 누적 비용에 두 번째 집이 빨강으로 칠할 때의 비용을 더한 값과 첫 번째 집이 파랑을 칠했을 때의 누적 비용에 두 번째 집이 빨강으로 칠할 때의 비용을 더한 값 중 더 작은 것으로 채워넣습니다. 당연히 89가 132보다 작기 때문에 cost 배열의 첫 번째 칸에는 89가 들어가게 됩니다.

 

 

cost에 들어가는 각 값들은, 해당 집에서 이 색깔을 선택했을 때 가질 수 있는 지금까지의 누적 비용의 최솟값을 뜻한다고 생각하시면 됩니다. 이런 식으로 N번 째 집까지의 누적 비용을 색깔 별로 구해줍니다. 그리고 cost 배열의 N 번째 값들 중 가장 작은 값을 최종적으로 출력해주면 됩니다.

 

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
 
class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N;
        N = Integer.parseInt(br.readLine());
 
        int i, j;
        int[][] arr = new int[N][3];
        int[][] cost = new int[N][3];
 
        String s;
        StringTokenizer st;
 
        for (i = 0; i < N; i++) { // arr 배열에 입력 값 저장
            s = br.readLine();
            st = new StringTokenizer(s);
            for (j = 0; j < 3; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        for (j = 0; j < 3; j++) { // cost[0]은 arr[0]과 동일
            cost[0][j] = arr[0][j];
        }
 
        for (i = 1; i < N; i++) { // cost[0]은 이미 채워넣었으니 1부터 N까지 반복하며
            if (cost[i - 1][1] < cost[i - 1][2]) // 빨강을 위한 cost[i][0]에 둘 중에 더 작은 쪽을 넣는데,
                cost[i][0] = cost[i - 1][1] + arr[i][0]; // cost[i-1][1]은 윗 집이 초록을 골랐을 때의 누적 비용이고,
            else
                cost[i][0] = cost[i - 1][2] + arr[i][0]; // cost[i-1][2]는 윗 집이 파랑을 골랐을 때의 누적 비용.
 
            if (cost[i - 1][0] < cost[i - 1][2])
                cost[i][1] = cost[i - 1][0] + arr[i][1];
            else
                cost[i][1] = cost[i - 1][2] + arr[i][1];
 
            if (cost[i - 1][0] < cost[i - 1][1])
                cost[i][2] = cost[i - 1][0] + arr[i][2];
            else
                cost[i][2] = cost[i - 1][1] + arr[i][2];
 
        }
 
        Arrays.sort(cost[N - 1]); // 정렬을 해서, 가장 작은 값을 출력
        System.out.println(cost[N - 1][0]);
    }
}