[백준] [1149] RGB거리 (JAVA) (DP)

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

1149번: RGB거리

---

---

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

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

---

※ JAVA 코드(RGB거리)

import java.io.*;
import java.util.*;

public class Main {
    static int[][] dp;
    static int[][] cost;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        // 집의 수
        Integer N = Integer.parseInt(br.readLine());

        // 초기화
        dp = new int[N][3];
        cost = new int[N][3];

        // 집의 수만큼 입력
        for(int h = 0; h < N; h++){
            st = new StringTokenizer(br.readLine());
            // 색상 값 {0: Red, 1: Green, 2: Blue}
            for(int c = 0; c < 3; c++){
                // 초기 값 (Red or Green or Blue)
                dp[h][c] = 0;
                // 초기 비용 0원부터 시작
                cost[h][c] = Integer.parseInt(st.nextToken());
            }
        }
        // 첫번째 집 Red
        dp[0][0] = cost[0][0];
        // 첫번째 집 Green
        dp[0][1] = cost[0][1];
        // 첫번째 집 Blue
        dp[0][2] = cost[0][2];

        int result = Math.min(dp(N-1, 0), dp(N-1, 1));
        result = Math.min(result, dp(N-1, 2));

        System.out.println(result);
    }

    static int dp(int h, int c){
        // 아직 값이 없을때
        if(dp[h][c] == 0){
            switch (c){
                case 0:
                    dp[h][c] = Math.min(dp(h-1, 1), dp(h-1, 2)) + cost[h][0];
                    break;
                case 1:
                    dp[h][c] = Math.min(dp(h-1, 0), dp(h-1, 2)) + cost[h][1];
                    break;
                case 2:
                    dp[h][c] = Math.min(dp(h-1, 0), dp(h-1, 1)) + cost[h][2];
                    break;
            }
        }
        return dp[h][c];
    }
}

---

※ 생각정리 (RGB거리)

전형적인 DP문제

맨 처음 집의 색상을 정한후 나올 수 있는 집의 경우를 생각해본다.

1. N이 빨간집인경우

- N-1은 녹색이거나 파란색일 수 있다.

- 두 경우중 더 작은 비용의 값을 구하고 N이 빨간집인 경우의 가중치를 더한다.

- dp[h][c] = Math.min(dp(h-1, 1), dp(h-1, 2)) + cost[h][0];

2. N이 녹색인 경우와 파란색인 경우는 위와 동일하다.

 

중요한 점은 N-1을 넣고 재귀를 돌며 계속해서 다음 값을 합해나간다.

 

 

-새벽코딩-