[백준] RGB거리 - 자바 Java

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

 

대충 N번째 집까지의 누적합에 그 다음 집의 최소 비용을 더한다는 개념에서 DP를 사용하면 될 것이라고 생각했다.

 

하지만 단순히 각 집마다 최소 비용을 선택해 누적합을 구하는 방법이 맞을까 고민해봤다.

아래 예제를 보면 아니라는 것을 알 수 있다.

예시 테스트케이스

 

첫 번째 경우처럼 집마다 최소 비용을 선택한 경우 누적합은 1 + 100 + 100 = 201이다.

1. 각 집마다 최소비용 선택

 

두 번째 경우 누적합은 100 + 1 + 1 = 102로 최소값을 갖는다. 

2. 다른 누적합 경우의 수

 

결과적으로 각 집의 최소 비용을 찾아 누적합을 구하는 것이 아니고, 모든 경우의 수의 누적합을 구해 그 중 최소값을 찾아야 한다.

---

1. 비용 계산에 필요한 Cost와 누적합을 저장할 DP를 각각 2차원 배열로 선언한다. 

 

2. DP 배열의 첫 번째 값은 색상별 첫번째 비용으로 초기화한다.

 

3. 점화식은 다음과 같다. 

    1. Red의 경우

       Cost[N][0] = min(Cost[N-1][1], Cost[N-1][2]) + Cost[N][0]

    2. Green의 경우

       Cost[N][1] = min(Cost[N-1][0], Cost[N-1][2]) + Cost[N][1]

    3. Blue의 경우

       Cost[N][2] = min(Cost[N-1][0], Cost[N-1][1]) + Cost[N][2]

 

전체 코드

import java.util.*;
import java.lang.Math;

public class Main
{
    final static int Red = 0;
    final static int Green = 1;
    final static int Blue = 2;
    
    static int[][] DP;
    static int[][] Cost;
    
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		
		Cost = new int[N][3];
		DP = new int[N][3];
		
		for(int i=0; i<N; i++) {
		    Cost[i][Red] = sc.nextInt();
		    Cost[i][Green] = sc.nextInt();
		    Cost[i][Blue] = sc.nextInt();
		}
		
		// DP의 첫번째 집 초기화
		DP[0][Red] = Cost[0][Red];
		DP[0][Blue] = Cost[0][Blue];
		DP[0][Green] = Cost[0][Green];
		
		System.out.print(Math.min(PaintCost(N- 1, Red), Math.min(PaintCost(N - 1, Green), PaintCost(N - 1, Blue))));
	}
	
	static int PaintCost(int N, int color) {
	    
	    if(DP[N][color] == 0) {
	        
	        if(color == Red) {
    	        DP[N][Red] = Math.min(PaintCost(N-1, Green), PaintCost(N-1, Blue)) + Cost[N][Red];
    	    } else if(color == Green) {
    	        DP[N][Green] = Math.min(PaintCost(N-1, Red), PaintCost(N-1, Blue)) + Cost[N][Green];
    	    } else {
    	        DP[N][Blue] = Math.min(PaintCost(N-1, Red), PaintCost(N-1, Green)) + Cost[N][Blue];
    	    }    
	    }
	    
	    return DP[N][color];
	}
}