[백준] 동적계획법 (1149 : RGB거리)

문제

---

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

1149번: RGB거리

해당 문제는 N개의 집을 R,G,B 3가지 색으로 칠하는 비용이 최소가 되도록 하는 문제이다.

하지만, 집이 3개일 때, R, G, R처럼 동일한 색이 중복되는 것은 가능하지만
R, R, G처럼 같은 색을 연속해서 사용할 수는 없다. 

해당 조건을 만족하면서 문제를 해결해보자!.

이번에도 Bottom-Up, Top-Down 두가지 방식을 모두 구현해보았다.

---

해설

---

Bottom-Up

---

 

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringBuilder sb = new StringBuilder();

    static int[][] rgb;
    static int[][] cost;
    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());
        rgb = new int[N][3];
        cost = new int[N][3];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 3; j++) {
                rgb[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        cost[0][0] = rgb[0][0];
        cost[0][1] = rgb[0][1];
        cost[0][2] = rgb[0][2];
        int min = 0;

        for (int i = 1; i < N; i++) {
            for (int j = 0; j < 3; j++) {
                if(j == 0)
                    cost[i][j] = Math.min(cost[i-1][1], cost[i-1][2])+rgb[i][j];
                else if(j == 1)
                    cost[i][j] = Math.min(cost[i-1][0], cost[i-1][2])+rgb[i][j];
                else
                    cost[i][j] = Math.min(cost[i-1][0], cost[i-1][1])+rgb[i][j];
            }
        }
        min = Math.min(Math.min(cost[N - 1][0], cost[N - 1][1]), cost[N-1][2]);
        sb.append(min);
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

---

예시)

row\color	R	G	B
1	26	40	83
2	49	60	57
3	13	89	99

위에서 말한 조건을 만족하기 위해서는,
2번째 행부터, 앞에서 선택된 색을 제외한 두 색의 비용을 비교하여 더 작은 값을 선택해야한다.
그리고, 더 작은 값에 현재 색의 비용을 더해주면, 이전 행들과 현재 행까지의 비용의 총합을 구하게 되는 것이다.

이런 식으로 마지막 행까지 계산하면, 마지막 행에 저장된 3개의 값은

마지막이 R인경우, G인경우, B인경우 중 최소의 비용이 저장되어 있다.

2번째 집	1번째 집	1번째 집 비용		결과
R	G	40	+ 49	89
R	B	83		132
G	R	26	+60	86
G	B	83		143
B	R	26	+57	83
B	G	40		97

위의 과정을 끝까지 진행하면, R(26) → B(57) → R(13) = 96 이 가장 최소의 비용인 것을 확인할 수 있다.

---

코드 설명

1. 첫번째 집은 자기 자신이 최솟값이므로, cost를 초기화해준다.
2. R일때는, 이전 집이 R이면 안되므로, G, B 중 최솟값을 선택하는 방식으로 조건문을 만들어준다.
3. 최소 비용으로 cost를 업데이트하며, 마지막에 선택되는 색이 R인경우, G인 경우, B인경우 3가지 중 
   최솟값을 선택하여 출력한다.

---

Top-Down

---

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringBuilder sb = new StringBuilder();

    static int[][] rgb;
    static int[][] cost;
    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());
        rgb = new int[N][3];
        cost = new int[N][3];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 3; j++) {
                rgb[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        cost[0][0] = rgb[0][0];
        cost[0][1] = rgb[0][1];
        cost[0][2] = rgb[0][2];
        dp1149(N-1, 0);
        dp1149(N-1, 1);
        dp1149(N-1, 2);

        int min = Math.min(Math.min(cost[N - 1][0], cost[N - 1][1]), cost[N-1][2]);
        sb.append(min);
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
    private static int dp1149(int N, int color){
        if(cost[N][color] == 0){
            if(color == 0)
                cost[N][color] = Math.min(dp1149(N-1, 1), dp1149(N-1, 2))+rgb[N][color];
            else if (color == 1)
                cost[N][color] = Math.min(dp1149(N-1, 0), dp1149(N-1, 2))+rgb[N][color];
            else
                cost[N][color] = Math.min(dp1149(N-1, 0), dp1149(N-1, 1))+rgb[N][color];
        }
        return cost[N][color];
    }
}

위와 동일하지만 재귀함수를 통해 구현하였다.

---

1. 위와 동일하게 첫번째 집은 자기 자신이 최솟값이므로 초기화해준다.
2. 이전 집들의 비용을 다시 구하지 않기 위해, 값을 저장해두고 사용하며,
   R인경우에 G, B 중 최솟값을 선택하는 것은 동일하다.

---

결론

---

이전 문제인 1912 : 연속합과 유사한 문제였기 때문에, 무난하게 해결할 수 있었던 것 같다!.

---