DynamicProgramming 백준 알고리즘 JAVA 1149 ‘RGB거리’ 문제풀이

Problem

RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이다. 각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠할 때 드는 비용의 최솟값을 구하는 프로그램을 작성하시오.

Input
첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로 칠할 때, 초록으로 칠할 때, 파랑으로 칠할 때 드는 비용이 주어진다. 비용은 1,000보다 작거나 같은 자연수이다.

Output
첫째 줄에 모든 집을 칠할 때 드는 비용의 최솟값을 출력한다.

Solution

N번째 집이 빨간색으로 칠했을 경우의 최소 비용은 N-1번째 집이 초록색 또는 파란색으로 칠했을 때 중 최소 비용 선택 + N번째의 빨간색 비용 ….

Code

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int[][] price = new int[n][3];
		int[][] dp = new int[n][3];
		
		for(int i = 0; i < price.length; i++) {
			price[i][0] = scan.nextInt();
			price[i][1] = scan.nextInt();
			price[i][2] = scan.nextInt();
		}
		
		dp[0][0] = price[0][0];
		dp[0][1] = price[0][1];
		dp[0][2] = price[0][2];
		for(int i = 1; i < n; i++) {
			dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + price[i][0];
			dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + price[i][1];
			dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + price[i][2];
		}
		
		System.out.println(Math.min(Math.min(dp[n-1][0], dp[n-1][1]), dp[n-1][2]));
	}
}