백준-1149번/RGB거리 (java)

우선 각각의 집의 RGB 비용을 저장 할 이차원 배열 RGB[n][3]을 만들어준다.

그리고  RGB와 크기가 같은 이차원 배열 dp[n][3]을 만들어준다.

 

 

dp문제는 조건에 따른 경우의 수를 누적해 오면서 맨 마지막 경우에 따른 뒤의 경우를 생각해봐야 한다.

 

3
26 40 83
49 60 57
13 89 99

이렇게 3개의 집이 있다고 생각해보자.

 

맨 마지막 집이 빨간색인 경우 ==> 이 전 집은 파랑OR초록이 왔을때의 최솟값

맨 마지막 집이 파란색인 경우 ==> 이 전 집은 빨강OR초록이 왔을때의 최솟값

맨 마지막 집이 초록색인 경우 ==> 이 전 집은 빨강OR파랑이 왔을때의 최솟값

 

이 때 전전 집(dp[n-2][?])을 생각하지 않아도 되는 이유 : 전전 집도 위 식과 똑같은 방식으로 앞 뒤 집과 똑같은 색을 피해 가는 경우이다.

 

이렇게 만든 점화식은 다음과 같다.

		dp[0][0]=RGB[0][0];
		dp[0][1]=RGB[0][1];
		dp[0][2]=RGB[0][2];
		
		for(int i=1; i<n; i++) {
			dp[i][0]=Math.min(dp[i-1][1],dp[i-1][2])+RGB[i][0];
			dp[i][1]=Math.min(dp[i-1][0],dp[i-1][2])+RGB[i][1];
			dp[i][2]=Math.min(dp[i-1][1],dp[i-1][0])+RGB[i][2];
			
		}

 

 

최소 비용을 구할때는 마지막 집이 R인 경우, G인 경우, B인 경우의 최솟값을 구해주면 된다. 

int min=dp[n-1][0];
		for(int i=0; i<3; i++) {
			if(min>dp[n-1][i]) {
				min=dp[n-1][i];
			}
		}

 

 

정답 코드

import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n=scanner.nextInt();
		int [][] RGB = new int[n][3];
		for(int i=0; i<n; i++) {
			for(int j=0; j<3; j++) {
			RGB[i][j]=scanner.nextInt();
			}
		}
		
		int[][] dp = new int[n][3];
		
		dp[0][0]=RGB[0][0];
		dp[0][1]=RGB[0][1];
		dp[0][2]=RGB[0][2];
		
		for(int i=1; i<n; i++) {
			dp[i][0]=Math.min(dp[i-1][1],dp[i-1][2])+RGB[i][0];
			dp[i][1]=Math.min(dp[i-1][0],dp[i-1][2])+RGB[i][1];
			dp[i][2]=Math.min(dp[i-1][1],dp[i-1][0])+RGB[i][2];
			
		}
		int min=dp[n-1][0];
		for(int i=0; i<3; i++) {
			if(min>dp[n-1][i]) {
				min=dp[n-1][i];
			}
		}
		
		System.out.println(min);
		
	}
}