[백준] JAVA - 1149.RGB거리

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

1149번: RGB거리

생각

N번째 집을 정해진 조건에 따라서 칠했을때 최소비용을 찾는 문제입니다. 처음에 dp를 1차원 배열로 설정하고 N개의 집을 색칠하는 최소비용을 계산하려다가 색칠하는 경우를 나눌수가 없어서 2차원 배열로 수정했습니다.

 

이때 집을 칠하는 경우는 총 세가지로 첫번째집을 빨간색으로 칠했다면 그 다음 집에 칠해야할 색은 조건에 따라 분기됩니다.

 

제가 정의한 dp는 dp[i][j] : i번째집을 j(0,1,2 : 빨강,초록,파랑)으로 칠했을때 최소비용 입니다. i번째 집을 어떤색으로 칠하는게 최소비용인지를 찾기 위해선 이 세가지 경우 중 최소값이 답이 됩니다.

 

집을 색칠할때 i번째 집은 i-1번과는 색깔이 달라야 하므로 만약 i번째집이 빨강으로 칠해졌다면 i-1번째 집은 파랑 이거나 초록으로 칠해져있습니다.

 

이를 점화식으로 나타내면 아래와 같습니다.

 

dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + i번집을 빨간색으로 칠하는 비용

dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + i번집을 초록색으로 칠하는 비용

dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + i번집을 파랑색으로 칠하는 비용

 

Java Code

package com.java.algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_1149_RGB거리 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int N = Integer.parseInt(br.readLine());
		
		int[][] dp = new int[1001][3];
		int[][] cost = new int[1001][3];
		
		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			cost[i][0] = Integer.parseInt(st.nextToken()); // R 비용
			cost[i][1] = Integer.parseInt(st.nextToken()); // G 비용
			cost[i][2] = Integer.parseInt(st.nextToken()); // B 비용
		}
		dp[1][0] = cost[1][0];
		dp[1][1] = cost[1][1];
		dp[1][2] = cost[1][2];
		
		for (int i = 2; i <= N; i++) {
			dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + cost[i][0]; //i번째 집을 빨간색으로 칠했을때
			dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + cost[i][1]; //i번째 집을 초록색으로 칠했을때
			dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + cost[i][2]; //i번째 집을 파랑색으로 칠했을때
		}
		int ans = Math.min(Math.min(dp[N][0], dp[N][1]), dp[N][2]); // 세가지중 가장 최소 비용
		System.out.println(ans);

	}

}