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

문제 : https://www.acmicpc.net/problem/1149

 

서로 인접한 집끼리 서로 다른 색(3가지 색을 사용할 수 있다)으로 칠할 때, 최소 비용을 구하는 문제이다.

 

입력

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

 

풀이

나이브하게 모든 조합을 모두 탐색한다고 생각해보면 O(3^N)의 복잡도를 가진다. N은 최대 1,000이므로 모든 조합을 탐색하는 것은 불가능한 것을 알 수 있다.

 

해당 문제는 DP를 활용하여 해결할 수 있다.  i 번째 집을 칠할 때, i-1번째 집까지 칠한 상태를 참고하는 방식이다.  DP 테이블은 i 번째 집을 칠할 때 3가지 색상에 대한 최소 비용을 업데이트하며 N번째 집까지 올라간다.

 

i번째 집을 칠할때, 가능한 경우의 수는 3가지(빨강, 초록, 파랑)이다. 빨강을 칠한다고 가정해보자. 연속된 두 집은 같은 색으로 칠할 수 없으므로, i -1 번째 집을 초록 혹은 파랑으로 칠했을 때의 비용 중, 더 작은 비용을 선택하고, i 번째 집을 빨강으로 색칠하는 단일 비용을 합해 DP 테이블에 저장한다. 3가지 색상에 대해 같은 작업을 수행하며 i를 1부터 N까지 올려가며 업데이트하면 쉽게 답을 구할 수 있다.

 

dp[N][0], dp[N][1], dp[N][2] 중 가장 작은 값을 출력한다.

 

소스 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int numberOfHouse = scanner.nextInt();
        int house[][] = new int[numberOfHouse][3];
        
        for(int i=0; i<numberOfHouse; i++){
            for(int j=0; j<3; j++){
                house[i][j]=scanner.nextInt();
            }
        }
        
        int sum[][] =new int[numberOfHouse][3];
        sum[0][0]=house[0][0]; sum[0][1]=house[0][1]; sum[0][2]=house[0][2];
        
        for(int i=1; i< sum.length; i++){
            sum[i][0]=Math.min(sum[i-1][1],sum[i-1][2])+house[i][0];
            sum[i][1]=Math.min(sum[i-1][0],sum[i-1][2])+house[i][1];
            sum[i][2]=Math.min(sum[i-1][0],sum[i-1][1])+house[i][2];
        }

        System.out.print(Math.min(sum[numberOfHouse-1][0],Math.min(sum[numberOfHouse-1][1],sum[numberOfHouse-1][2])));
    }
}