백준 1149 - RGB거리

Java

1149 번 - RGB거리

문제

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

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

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

접근 방법

총 N개의 집을 R, G, B 셋 중 하나의 색으로 색칠하며, i번째 집은 i - 1번째 집과 색을 다르게 하면 된다.
총 3개의 색을 칠 할 수 있으므로, 최종적으로 3개의 색을 칠하는 경우를 다 생각해본다고 생각하자.
만약 마지막에 빨강을 칠했다면, 그 이전 집은 초록, 파랑 둘 중 비용이 적은 색을 칠했을 것이다.
따라서, 2번째 집부터, i - 1번째 집의 색 중 비용이 적을 색을 택하여 계속하여 더하는 식으로, 마지막 n 번째 집에 R, G ,B 색을 각각 칠한 경우를 판별하여 그 중 가장 비용이 적은 결과를 택한다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, result;
	static int[][] rgb, dp;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	n = stoi(br.readLine());
    	rgb = new int[n][3];
    	dp = new int[n][3];
    	
    	for(int i = 0; i < n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		for(int j = 0; j < 3; j++) {
    			rgb[i][j] = stoi(stk.nextToken());
    		}
    	}
    	
    	dp[0][0] = rgb[0][0];	// R 색으로 칠하기
    	dp[0][1] = rgb[0][1];	// G 색으로 칠하기
    	dp[0][2] = rgb[0][2];	// B 색으로 칠하기
    	
		// N개의 집을 색칠한다.
    	for(int i = 1; i < n; i++) {
			// i 번째 집에 R G B 색을 칠하는 비용을 측정한다.
    		for(int j = 0; j < 3; j++) {
				// i - 1번째 집의 색 중 현재 칠 할려는 색과 다른 색을 비교한다
    			for(int k = 0; k < 3; k++) {
    				if(j != k) {
						// 이전 색과 같다면 넘긴다
    					if(dp[i][j] == 0)
    						dp[i][j] = dp[i - 1][k] + rgb[i][j];
    					else	// 가장 비용이 적게 드는 (i - 1) 색을 현재 (i)색과 더하여 저장
    						dp[i][j] = Math.min(dp[i - 1][k] + rgb[i][j], dp[i][j]);
    				}
    			}
    		}
    	}
    	
    	int result = Integer.MAX_VALUE;
    	for(int i = 0; i < 3; i++) {		// 총 계산 된 최종 r g b 색 중 가장 비용이 적은 것을 택한다.
    		result = Math.min(result, dp[n-1][i]);
    	}
    	System.out.println(result);
    	br.close();
	}

	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

난이도

⭐⭐★★★

후기

개선할 점