RGB 거리 2

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

덜 formal하지만, 보다 느낌오게 문제를 설명하면 아래와 같다.

• 1~N번 집을 순서대로 원형으로 배치한 뒤, 색칠 할 때 이웃한 집끼리 다른 색으로 칠하는 최소 비용은?

DP로 풀어줄 수 있는데, 첫 집 / 끝 집 처리가 은근히 귀찮다.

우선, 첫 집 / 끝 집을 무시하고(즉, 일자로 늘어선 집들을 칠하는 것 처럼) 아래와 같이 CACHE를 정의하였다.

• CACHE[i][first][last]: i번 째 집까지, 첫 집의 색을 first로, 끝 집의 색을 last로 하여 색칠할 때 최소비용

첫 집, 끝 집 조건을 무시하므로 아래와 같이 아주 쉽게 점화식을 세워줄 수 있다.

• CACHE[i+1][first][last] = min(CACHE[i][first][colour] + COST[i+1][last])(단, colour != last)

이와 같이 풀어준 뒤, min(CACHE[N][first][last])(where first != last)를 구해주면 답을 구할 수 있다.

#include <cstdio>
#include <algorithm>

using namespace std;

const int kMaxN = 1000;
const int kR = 0;
const int kG = 1;
const int kB = 2;

int N;
int COST[kMaxN][3];
int CACHE[kMaxN][3][3];

int main(void)
{
  // Initialize
  for (int i = 0; i < kMaxN; ++i)
  {
    for (int first = 0; first < 3; ++first)
    {
      for (int last = 0; last < 3; ++last)
      {
        CACHE[i][first][last] = kMaxN * kMaxN + 1;
      }
    }
  }

  // Read Input
  scanf(" %d", &N);
  for (int i = 0; i < N; ++i)
  {
    scanf(" %d %d %d", &COST[i][kR], &COST[i][kG], &COST[i][kB]);
  }

  // Base case
  for (int first = 0; first < 3; ++first)
  {
    for (int last = 0; last < 3; ++last)
    {
      if (first != last)
      {
        CACHE[1][first][last] = COST[0][first] + COST[1][last];
      }
    }
  }

  // Dp
  for (int i = 2; i < N; ++i)
  {
    for (int first = 0; first < 3; ++first)
    {
      for (int last = 0; last < 3; ++last)
      {
        int& target = CACHE[i][first][last];

        if (last == kR)
        {
          target = min(target, CACHE[i - 1][first][kG] + COST[i][kR]);
          target = min(target, CACHE[i - 1][first][kB] + COST[i][kR]);
        }
        if (last == kG)
        {
          target = min(target, CACHE[i - 1][first][kR] + COST[i][kG]);
          target = min(target, CACHE[i - 1][first][kB] + COST[i][kG]);
        }
        if (last == kB)
        {
          target = min(target, CACHE[i - 1][first][kR] + COST[i][kB]);
          target = min(target, CACHE[i - 1][first][kG] + COST[i][kB]);
        }
      }
    }
  }

  // Solve
  int ans = kMaxN * kMaxN + 1;
  for (int first = 0; first < 3; ++first)
  {
    for (int last = 0; last < 3; ++last)
    {
      if (first != last)
      {
        ans = min(ans, CACHE[N - 1][first][last]);
      }
    }
  }

  printf("%d\n", ans);

  return 0;
}