[백준 1149번] RGB거리 (C++)

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

1149번: RGB거리

---

RGB거리 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다.

집의 수가 최대 1000개이고, 각 집은 3개의 색을 선택할 수 있으므로, 백트래킹을 이용할 경우 시간초과가 발생할 수 있습니다. 

 

다이나믹 프로그래밍은 테이블 정의, 점화식 작성, 초기값 정하기 구분할 수 있습니다.

1. 테이블 정의
   • d[i][j]는 i번째 집의 색을 j로 칠할 때, 모든 집을 칠하는 비용의 최솟값입니다. (j는 빨강, 초록, 파랑을 나타냄)
   • 출력할 값은 n번째 집을 빨강, 초록, 파랑으로 칠했을 때의 최소 비용 중 가장 작은 값을 출력하면 됩니다.
   • 즉, min(d[n][1], d[n][2], d[n][3])입니다.
2. 점화식 작성
   • 문제에서 인접한 집의 색은 서로 달라야 한다는 조건이 있습니다.
     이는 n - 1과 n을 서로 다른 색으로 칠하면 만족시킬 수 있습니다.
     (n - 1과 n의 색이 서로 다르면, n - 2와 n - 1의 색이 다르므로, n - 1과 인접한 집의 색이 서로 다름)
   • i번째 집을 빨강으로 칠했을 때 모든 집을 칠하는 비용의 최솟값은
     (i - 1번째 집의 색을 초록 또는 파랑으로 칠했을 때, 모든 집을 칠하는 비용의 최솟값) + (i번째 집을 빨강으로 칠하는 비용)입니다. 
   • 따라서 아래와 같습니다.

   d[i][1] = c[i][1] + min(d[i - 1][2], d[i - 1][3])
   d[i][2] = c[i][2] + min(d[i - 1][1], d[i - 1][3])
   d[i][3] = c[i][3] + min(d[i - 1][1], d[i - 1][2])

3. 초기식 정하기
   • 점화식에 d[n - 1][1], d[n - 1][2], d[n - 1][3]이 등장하므로, d[1][1], d[1][2], d[1][3]의 값을 정해주면 됩니다.

아래는 전체 코드입니다.

#include <bits/stdc++.h>
using namespace std;

int d[1001][4]; // d[i][j]는 i번째 집의 색을 j로 칠할 때, 모든 집을 칠하는 비용의 최솟값
int c[1001][1001];  // c[i][j]는 i번째 집의 색을 j로 칠할 때의 비용
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= 3; j++)
            cin >> c[i][j]; // 각 집을 빨강, 초록, 파랑으로 칠하는 비용

    for(int i = 1; i <= 3; i++) d[1][i] = c[1][i];  // 1번째 집의 색을 i으로 칠할 때의 비용(초기값)
    for(int i = 2; i <= n; i++){
        // i번째 집을 빨강으로 칠했을 때 모든 집을 칠하는 비용의 최솟값은, 
        // i - 1번째 집의 색을 초록 또는 파랑으로 칠했을 때, 모든 집을 칠하는 비용의 최솟값 + i번째 집을 빨강으로 칠하는 비용
        d[i][1] = c[i][1] + min(d[i - 1][2], d[i - 1][3]); 
        d[i][2] = c[i][2] + min(d[i - 1][1], d[i - 1][3]); // i번째 집을 초록으로 칠하는 경우
        d[i][3] = c[i][3] + min(d[i - 1][1], d[i - 1][2]); // i번째 집을 파랑으로 칠하는 경우
    }
    cout << min({d[n][1], d[n][2], d[n][3]});
}