백준 17404번 - RGB거리 2 [C++]

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

 

솔브드 CLASS 5를 미는 도중 만난 문제.

약 두 달 전쯤 수업 시간에 풀다가 아이디어가 안 떠올랐었다.

그러다 오늘 다시 도전.

 

[아이디어]

RGB거리 문제와 같이 $1$번 집부터 $N - 1$번째 집까지 현재 칠해야 할 집의 바로 앞 집의 색만 신경써서 채워나가고, $N$번 집을 칠할 때만 $N - 1$번 집과 $1$번 집의 색을 고려해주면 된다.

근데 여기서 $1$번 집을 고려한다는 것은 $1$번 집에 어떤 색을 칠했었는지 알고 있어야 한다는 의미인데 어떻게 알 수 있을까?

$dp[i][j]$ - $1$ ~ $i$번째 집까지 색을 칠하고, $i$번째 집에 색 $j$를 칠할 경우 최소 비용

단순하게 RGB거리와 같이 0번 집이 있다고 가정하고 첫 번째 집부터 0번 색을 칠할 경우, 1번 색을 칠할 경우, 2번 색을 칠할 경우 모두 dp에 기록하게 되면 나중에 첫 번째 집에 무슨 색을 칠했는 지 알 수가 없다.

=> 참고 코드

// RGB거리 코드 中
for (int i = 1; i <= N; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    dp[i][0] = a + min(dp[i-1][1], dp[i-1][2]);
    dp[i][1] = b + min(dp[i-1][0], dp[i-1][2]);
    dp[i][2] = c + min(dp[i-1][0], dp[i-1][1]);
}

 

그러면 $1$번 집의 색을 미리 지정한 다음 작업을 수행하면 되지 않을까?

 

맞다. $1$번 집의 색을 지정하고, $2$ ~ $N$번째 집에 대해 기존 RGB거리 문제처럼 작업을 수행하면 된다.

 

그리고 정답을 도출할 때, $1$번 집의 색을 $0$으로 칠했다면, $dp[N][1]$과 $dp[N][2]$ 둘 중 최솟값을 취하면 된다.

 

[C++17 코드]

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

#ifdef LOCAL_TEST
constexpr bool isLOCAL = true;
#else
constexpr bool isLOCAL = false;
#endif

#define debug if constexpr (isLOCAL) cerr

typedef long long ll;
typedef pair<int, int> pii;
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()

const int MOD = 1e9 + 7;
const int INF = 1e9;

void solve() {
  int n; cin >> n;
  vector<array<int, 3>> vec(n + 1), dp(n + 1);
  for (int i = 1; i <= n; i++) {
    auto &[x, y, z] = vec[i];
    cin >> x >> y >> z;
  }
  int ans = INF;
  for (int i = 0; i < 3; i++) { // 1번 집 색상 지정
    dp[1][i] = vec[1][i];
    dp[1][(i + 1) % 3] = dp[1][(i + 2) % 3] = INF;
    for (int j = 2; j <= n; j++) {
      auto [x, y, z] = vec[j];
      dp[j][0] = min(dp[j - 1][1], dp[j - 1][2]) + x;
      dp[j][1] = min(dp[j - 1][0], dp[j - 1][2]) + y;
      dp[j][2] = min(dp[j - 1][0], dp[j - 1][1]) + z;
    }
    for (int j = 0; j < 3; j++) if (i != j) ans = min(ans, dp[n][j]);
  }
  cout << ans;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
  debug << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  return 0;
}