[BOJ] 17404 - RGB거리 2

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

BOJ - RGB거리 2

문제 유형: 다이나믹 프로그래밍

문제 난이도: Gold IV

시간 제한: 0.5초

메모리 제한: 128MB

 

문제

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보다 작거나 같은 자연수이다.

 

출력

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

 

풀이

dp[i][j][k] = i번째집의 이번에 넣는 색깔이 j이고 시작색깔이 k인 상태의 최소 비용이다.

 

처음 dp[0][j][k]인 경우에서, j == k인 경우를 제외하고는 모두 불가능하므로 큰 수를 넣는다.

j == k인 경우는 각각 0, 1, 2에 대해서 각각의 r, g, b로 채운다.

 

그리고, 중간의 n-2개의 집에 대해서 입력을 받아서 유효한 값을 받아온다.

dp[i][j][k]에 대해서, 같은 k에 대해 다른 j를 가진 i-1로부터 최소값을 가져오고, 이번 색깔비용과 더해서 저장하면 된다.

 

마지막 r, g, b를 받고는, dp[n-1][j][k]에서 j==k인 경우는 불가능하므로 큰 수로 채운다.

이외에는, 이전처럼 최소값을 가져와서 이번 색깔비용과 더해서 저장한다.

 

최종적으로, dp[n-1]의 가장 작은 값을 가져와서 출력해주면 된다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin >> n;

  // dp[step][last][start]
  vector<vector<vector<int>>> dp(n, vector<vector<int>>(3, vector<int>(3, 0)));
  int r, g, b;
  cin >> r >> g >> b;
  dp[0][0][0] = r;
  dp[0][1][1] = g;
  dp[0][2][2] = b;
  dp[0][0][1] = 1e9;
  dp[0][0][2] = 1e9;
  dp[0][1][0] = 1e9;
  dp[0][1][2] = 1e9;
  dp[0][2][0] = 1e9;
  dp[0][2][1] = 1e9;

  for (int i = 1; i < n - 1; ++i) {
    cin >> r >> g >> b;
    dp[i][0][0] = min(dp[i - 1][1][0], dp[i - 1][2][0]) + r;
    dp[i][0][1] = min(dp[i - 1][1][1], dp[i - 1][2][1]) + r;
    dp[i][0][2] = min(dp[i - 1][1][2], dp[i - 1][2][2]) + r;
    dp[i][1][0] = min(dp[i - 1][2][0], dp[i - 1][0][0]) + g;
    dp[i][1][1] = min(dp[i - 1][2][1], dp[i - 1][0][1]) + g;
    dp[i][1][2] = min(dp[i - 1][2][2], dp[i - 1][0][2]) + g;
    dp[i][2][0] = min(dp[i - 1][0][0], dp[i - 1][1][0]) + b;
    dp[i][2][1] = min(dp[i - 1][0][1], dp[i - 1][1][1]) + b;
    dp[i][2][2] = min(dp[i - 1][0][2], dp[i - 1][1][2]) + b;
  }

  cin >> r >> g >> b;

  dp[n - 1][0][0] = INT_MAX;
  dp[n - 1][1][0] = min(dp[n - 2][0][0], dp[n - 2][2][0]) + g;
  dp[n - 1][2][0] = min(dp[n - 2][0][0], dp[n - 2][1][0]) + b;
  dp[n - 1][0][1] = min(dp[n - 2][1][1], dp[n - 2][2][1]) + r;
  dp[n - 1][1][1] = INT_MAX;
  dp[n - 1][2][1] = min(dp[n - 2][0][1], dp[n - 2][1][1]) + b;
  dp[n - 1][0][2] = min(dp[n - 2][1][2], dp[n - 2][2][2]) + r;
  dp[n - 1][1][2] = min(dp[n - 2][0][2], dp[n - 2][2][2]) + g;
  dp[n - 1][2][2] = INT_MAX;

  int ans = INT_MAX;
  for (int i = 0; i < 3; ++i) {
    for (int j = 0; j < 3; ++j) {
      ans = min(ans, dp[n - 1][i][j]);
    }
  }

  cout << ans << "\n";

  return 0;
}