[BOJ/DP] 백준 1149 - RGB 거리 / 17404 - RGB 거리 2 (Java)

1149 - RGB 거리

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

문제

RGB 거리에는 집이 N개 있음/ 거리는 선분으로 나타낼 수 있고 1 ~ N번 집 순서대로 있음
집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 함
/ 각각의 집을 rgb로 칠하는 비용 주어졌을 때 규칙 만족하면서 모든 집 칠하는 비용의 최솟값
- 1번 집 색 != 2번 집 색
- N번 집 색 != N-1번 집 색
- i (2 <= i <= N-1) 집 색 != i - 1번, i + 1번

입력
첫째 줄: 집의 수 N (2 <= N <= 1,000)
둘째 줄 ~ N개 줄: rgb로 칠하는 비용 (<= 1,000)
출력: 모든 집을 칠하는 비용의 최솟값

---

풀이

• 색 인덱스: 0 (빨강) / 1 (초록) / 2(파랑)
• `dp[i][j]`: i번째 집까지 칠했을 때, i번 째 집의 색이 j일 때의 최소 비용
  • `dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + r`
    => 현재 집 색: 0 -> 이전 집 가능한 색: 1 / 2
  • `dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + g`
    => 현재 집 색: 1 -> 이전 집 가능한 색: 0 / 2
  • `dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + b`
    => 현재 집 색: 2 -> 이전 집 가능한 색: 0 / 1

---

예시

3 / 26 40 83 / 49 60 57 / 13 89 99

• 인접한 집끼리 색이 달라야 함
• 첫 번째 집 != 마지막 집

 

가능한 조합(집123)

• RGB = 26 + 60 + 99 = 185
• RGB = 26 + 57 + 89 = 172
• GRB = 40 + 49 + 99 = 188
• GBR = 40 + 57 + 13 = 110
• BRG = 83 + 49 + 89 = 221
• BGR = 83 + 60 + 13 = 156

=> 최소 비용 = 110

---

코드

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

// RGB 거리
public class boj_1149 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[][] dp = new int[N + 1][3];

        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int g = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + r;
            dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + g;
            dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + b;
        }

        System.out.println(Math.min(dp[N][0], Math.min(dp[N][1], dp[N][2])));
    }
}

---

17404 - RGB 거리 2

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

문제

RGB 거리에는 집이 N개 있음/ 거리는 선분으로 나타낼 수 있고 1 ~ N번 집 순서대로 있음
집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 함
/ 각각의 집을 rgb로 칠하는 비용 주어졌을 때 규칙 만족하면서 모든 집 칠하는 비용의 최솟값
- 1번 집 색 != 2번 집 색,  N번 집 색
- N번 집 색 != N-1번 집 색
- i (2 <= i <= N-1) 집 색 != i - 1번, i + 1번

입력
첫째 줄: 집의 수 N (2 <= N <= 1,000)
둘째 줄 ~ N개 줄: rgb로 칠하는 비용 (<= 1,000)
출력: 모든 집을 칠하는 비용의 최솟값

---

풀이

• 색 인덱스: 0 (빨강) / 1 (초록) / 2(파랑)
• `cost[i][j]`: i번째 집을 색 j로 칠했을 때 드는 비용
• `dp[i][j]`: i번째 집까지 칠했을 때, i번째 집이 색 j일 때의 최소 누적 비용

 

첫 번째 집 색 r/g/b일 때 모든 경우

• 첫 번째 집은 `first`색만 가능하고 나머지 색 불가능
  • ex. `first = 0` -> `dp[1][색상] = cost[1][0]` / 나머지 `INF`
• 2번 집 ~ N번 집
  • `dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + cost[i][0]`
    => 현재 집 색: 0 -> 이전 집 가능한 색: 1 / 2
  • `dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + cost[i][1]`
    => 현재 집 색: 1 -> 이전 집 가능한 색: 0 / 2
  • `dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + cost[i][2]`
    => 현재 집 색: 2 -> 이전 집 가능한 색: 0 / 1
• 마지막 집은 첫 번째 집과 다른 색만 가능
  • ex. `frist = 0` -> 마지막 집은 1, 2만 가능

=> 인접한 집끼리 색이 다르다는 조건만 반영해서 dp 계산

-> 모든 dp 계산 끝난 후 첫 번째 집과 마지막 집 색이 같으면 건너뜀(원형 조건)

for (int first = 0; first < 3; first++) {
    int[][] dp = new int[N + 1][3];

    for (int c = 0; c < 3; c++) {
        if (c == first) dp[1][c] = cost[1][c];
        else dp[1][c] = INF;
    }

    for (int i = 2; i <= N; i++) {
        dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + cost[i][0];
        dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + cost[i][1];
        dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + cost[i][2];
    }

    for (int last = 0; last < 3; last++) {
        if (last == first) continue;
        ans = Math.min(ans, dp[N][last]);
    }
}

---

코드

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

// RGB 거리 2
public class boj_17404 {
    static final int INF = 1_000_000_000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[][] cost = new int[N + 1][3];

        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            cost[i][0] = Integer.parseInt(st.nextToken());
            cost[i][1] = Integer.parseInt(st.nextToken());
            cost[i][2] = Integer.parseInt(st.nextToken());
        }

        int ans = INF;
        for (int first = 0; first < 3; first++) {
            int[][] dp = new int[N + 1][3];

            for (int c = 0; c < 3; c++) {
                if (c == first) dp[1][c] = cost[1][c];
                else dp[1][c] = INF;
            }

            for (int i = 2; i <= N; i++) {
                dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + cost[i][0];
                dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + cost[i][1];
                dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + cost[i][2];
            }

            for (int last = 0; last < 3; last++) {
                if (last == first) continue;
                ans = Math.min(ans, dp[N][last]);
            }
        }

        System.out.println(ans);
    }
}