백준 1149번) RGB거리 java

분석

---

기본적인 DP 문제이다. 

탑다운 방식으로 하면 쉽게 풀 수 있는데 단순 비교해서 dp 배열에 큰 값을 넣어주면 된다. (구현하는 과정이 좀 귀찮았다..)

 

집이 2개 있을 때, 

두번째 집이 R 인 경우와 첫번째 집이 G,B인 경우 중 작은 값을 DP배열에 넣어준다.

두번째 집이 G 인 경우와 첫번째 집이 R,B인 경우 중 작은 값을 DP배열에 넣어준다.

두번째 집이 B 인 경우와 첫번째 집이 R,G인 경우 중 작은 값을 DP배열에 넣어준다.

 

이렇게 하면 DP에 각 경우에 대한 최소값이 들어간다.

 

집이 3개 있을 때, 

세번째 집이 R 인 경우와 두번째 집이 G,B인(DP배열에서) 경우 중 작은 값을 DP배열에 넣어준다.

세번째 집이 G 인 경우와 두번째 집이 R,B인(DP배열에서) 경우 중 작은 값을 DP배열에 넣어준다.

세번째 집이 B 인 경우와 두번째 집이 R,G인(DP배열에서) 경우 중 작은 값을 DP배열에 넣어준다.

 

이렇게 하면 자동적으로 각각의 집을 칠하는 경우에 대한 최솟값이 마지막 집 인덱스의 DP 배열에 들어가게 된다.

 

마지막 집까지 이렇게 구해준 다음에 DP[집][R] , DP[집][G] , DP[집][B] 중 최솟값을 넣어주면 된다.

 

코드

---

import java.util.Scanner;

import static java.lang.Math.*;

public class Main {

    static Integer[][] dp;
    static int[][] value;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int num = sc.nextInt();

        dp = new Integer[num+1][3];
        value = new int[num+1][3];

        for(int i=1;i<=num;i++){
            for(int j=0;j<=2;j++){
                value[i][j] = Integer.parseInt(sc.next());
            }
        }
        dp[1][0] = value[1][0];
        dp[1][1] = value[1][1];
        dp[1][2] = value[1][2];
        System.out.println(min(dp(num,0),min(dp(num,1),dp(num,2))));

    }

    static int dp(int num,int seq){

        if(dp[num][seq] == null){
            if(seq == 0){
                dp[num][0] = min(dp(num-1,1) + value[num][seq],dp(num-1,2) + value[num][seq]);
            }
            if(seq == 1){
                dp[num][1] = min(dp(num-1,0) + value[num][seq],dp(num-1,2) + value[num][seq]);
            }
            if(seq == 2){
                dp[num][2] = min(dp(num-1,0) + value[num][seq],dp(num-1,1) + value[num][seq]);
            }
        }

        return dp[num][seq];
    }

}