[ BOJ 17404 ] RGB거리 2 ( JAVA )

문제

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

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

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

입력

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

 

출력

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

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
0.5 초 (추가 시간 없음)	128 MB	10491	6088	4990	58.084%

---

접근 :  RGB 거리 문제를 먼저 풀어보는 것을 권장한다. R,G,B 별로 각각 배열을 만들어야 한다. 즉, 기존 RGB 문제처럼 i(1 <= i <= N)번째 색칠한 집이 R인 경우, G인경우, B인 경우로 나누어 생각할 수 있다. 주어진 규칙에 따라 i번째 집을 R로 색칠하는 경우의 최소 비용은 i-1번째 집을 G, B로 색칠한 비용 중 최솟값 + R로 색칠하는 비용으로 나타낼 수 있다.

 

// i번째 집을 각각 색으로 칠하는 최소 비용을 구하는 점화식은 다음과 같다
dp_r[i] = Math.min( dp_g[i-1], dp_b[i-1] ) + cost_r[i];
dp_g[i] = Math.min( dp_r[i-1], dp_b[i-1] ) + cost_g[i];
dp_b[i] = Math.min( dp_g[i-1], dp_r[i-1] ) + cost_b[i];

 

 

이 점화식을 기본으로 두고, 주어진 첫번째 조건(1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다.)을 만족하기 위해서는 1번 집을 어떤 색으로 칠했는지 알고 있어야 한다.

따라서 첫번째 집을 R로 칠하는 경우, G로 칠하는 경우, B로 칠하는 경우로 각각 나누어서 문제를 해결하였다.

 

구현   

 

1) dp 초깃값 갱신

• 행번호에 따라 처음 집의 dp값을 지정

        // dp 초깃값 갱신
        // 0행: 1번째 집을 R로 색칠하는 경우이므로 다른 색으로 칠하는 비용은 INF로 처리
        dp_r[0][1] = dt[0][1];
        dp_g[0][1] = INF;
        dp_b[0][1] = INF;

        // G로 출발하는 경우
        dp_r[1][1] = INF;
        dp_g[1][1] = dt[1][1];
        dp_b[1][1] = INF;

        // B로 출발하는 경우
        dp_r[2][1] = INF;
        dp_g[2][1] = INF;
        dp_b[2][1] = dt[2][1];

2) 점화식 사용

• 위에서 구한 점화식을 이용하여 n-1 번 집까지의 최소 색칠 비용을 구함
  

            // 기본 점화식을 사용하여 n-1번 집까지의 최소 색칠 비용을 구함
            for (int j = 2; j <= n - 1; j++) {

                dp_r[i][j] = Math.min(dp_g[i][j - 1], dp_b[i][j - 1]) + dt[0][j];
                dp_g[i][j] = Math.min(dp_r[i][j - 1], dp_b[i][j - 1]) + dt[1][j];
                dp_b[i][j] = Math.min(dp_g[i][j - 1], dp_r[i][j - 1]) + dt[2][j];

            }

 

 

 

• 1번 집의 색( 행 번호)를 고려하여 n번째 집의 최소 색칠 비용을 구함

            // 마지막 n번째 집을 색칠할 때는 1번 집의 색(2차원 배열의 행)을 고려해 같은 색인 경우 INF로 처리함
            dp_r[i][n] = Math.min(dp_g[i][n - 1], dp_b[i][n - 1]) + ((i == 0) ? INF : dt[0][n]);
            dp_g[i][n] = Math.min(dp_r[i][n - 1], dp_b[i][n - 1]) + ((i == 1) ? INF : dt[1][n]);
            dp_b[i][n] = Math.min(dp_g[i][n - 1], dp_r[i][n - 1]) + ((i == 2) ? INF : dt[2][n]);

---

제출 결과

---

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * RGB거리 2
 */

public class BOJ17404 {


    static int dp_r[][], dp_g[][], dp_b[][];
    static int n;

    static final int INF = 10000000;

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(bufferedReader.readLine());

        // 2차원 배열의 각각 행은 1번 집을 어떤 색으로 칠했는지를 나타낸다.
        // 즉, 0행은 R, 1행은 G, 2행은 B로 1번 집을 색칠했다는 것이다.
        dp_r = new int[3][n+1];
        dp_g = new int[3][n+1];
        dp_b = new int[3][n+1];

        // 칠하는 비용으로 0행은 R, 1행은 G, 2행은 B로 칠하는 비용을 저장
        int[][] dt = new int[3][n+1];

        for (int i = 1; i <= n; i++) {
            String[] s = bufferedReader.readLine().split(" ");

            dt[0][i] = Integer.parseInt(s[0]); // R로 칠하는 비용
            dt[1][i] = Integer.parseInt(s[1]); // G로 칠하는 비용
            dt[2][i] = Integer.parseInt(s[2]); // B로 칠하는 비용
        }

        
        // dp 초깃값 갱신
        // 0행: 1번째 집을 R로 색칠하는 경우이므로 다른 색으로 칠하는 비용은 INF로 처리
        dp_r[0][1] = dt[0][1];
        dp_g[0][1] = INF;
        dp_b[0][1] = INF;

        // G로 출발하는 경우
        dp_r[1][1] = INF;
        dp_g[1][1] = dt[1][1];
        dp_b[1][1] = INF;

        // B로 출발하는 경우
        dp_r[2][1] = INF;
        dp_g[2][1] = INF;
        dp_b[2][1] = dt[2][1];


        int result = INF;


        for (int i = 0; i < 3; i++) {

            // 기본 점화식을 사용하여 n-1번 집까지의 최소 색칠 비용을 구함
            for (int j = 2; j <= n - 1; j++) {

                dp_r[i][j] = Math.min(dp_g[i][j - 1], dp_b[i][j - 1]) + dt[0][j];
                dp_g[i][j] = Math.min(dp_r[i][j - 1], dp_b[i][j - 1]) + dt[1][j];
                dp_b[i][j] = Math.min(dp_g[i][j - 1], dp_r[i][j - 1]) + dt[2][j];

            }

            // 마지막 n번째 집을 색칠할 때는 1번 집의 색(2차원 배열의 행)을 고려해 같은 색인 경우 INF로 처리함
            dp_r[i][n] = Math.min(dp_g[i][n - 1], dp_b[i][n - 1]) + ((i == 0) ? INF : dt[0][n]);
            dp_g[i][n] = Math.min(dp_r[i][n - 1], dp_b[i][n - 1]) + ((i == 1) ? INF : dt[1][n]);
            dp_b[i][n] = Math.min(dp_g[i][n - 1], dp_r[i][n - 1]) + ((i == 2) ? INF : dt[2][n]);

            // 최솟값 구하기
            result = Math.min(result, Math.min(dp_r[i][n], Math.min(dp_g[i][n], dp_b[i][n])));
        }

        // 결과 출력
        System.out.println(result);
    }


}

---

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

17404번: RGB거리 2

---