백준 1149번 - RGB거리

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

1149번: RGB거리

 

 

 

 

 

상향식 or 하향식으로 푸는 DP 개념을 안다면 금방 쉽게 풀린다.

 

cost 배열과 크기가 같은 2차원의 dp 배열에 dp[i][j]까지의 비용의 합을 저장한다.

 

1. dp 배열의 0행 : 1번 집의 R, G, B 값을 저장한다.

2. dp 배열의 1 ~ N-1행

 - R을 선택할 경우 : 현재의 행에서 R을 선택할 경우의 비용에 이전 행에서 G를 선택했을 경우의 비용의 합과 이전 행에서 B를 선택했을 경우의 비용의 합 중 최솟값을 더한다.

 - G를 선택할 경우 : 현재의 행에서 G을 선택할 경우의 비용에 이전 행에서 R을 선택했을 경우의 비용의 합과 이전 행에서 B를 선택했을 경우의 비용의 합 중 최솟값을 더한다.

 - B를 선택할 경우 : 현재의 행에서 G을 선택할 경우의 비용에 이전 행에서 R을 선택했을 경우의 비용의 합과 이전 행에서 G를 선택했을 경우의 비용의 합 중 최솟값을 더한다.

 

정답(최솟값)은 N - 1행에서 최종적으로 R을 선택했을 경우, G를 선택했을 경우, B를 선택했을 경우 중 최솟값이다.

 

 

 

 

 

코드

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

public class RGBStreet {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		int[][] cost = new int[N][3];
		
		for(int i = 0; i < N; i++) {
			String[] input = br.readLine().split(" ");
			
			for(int j = 0; j < 3; j++) {
				cost[i][j] = Integer.parseInt(input[j]);
			}
		}
		
		int[][] dp = new int[N][3];
		
		dp[0][0] = cost[0][0];
		dp[0][1] = cost[0][1];
		dp[0][2] = cost[0][2];
				
		for(int i = 1; i < N; i++) {
			dp[i][0] = cost[i][0] + Math.min(dp[i - 1][1], dp[i - 1][2]);
			dp[i][1] = cost[i][1] + Math.min(dp[i - 1][0], dp[i - 1][2]);
			dp[i][2] = cost[i][2] + Math.min(dp[i - 1][0], dp[i - 1][1]);	
		}
		
		int min = Math.min(dp[N - 1][0], Math.min(dp[N - 1][1], dp[N - 1][2]));
		
		System.out.println(min);
	
	}

}

 

 

 

 

 

결과