Dance Dance Revolution

Problme link: https://www.acmicpc.net/problem/2342

그닥 어렵지 않게 풀 수 있는 DP 문제이다.

아래와 같이 CACHE를 정의하였다.

• CACHE[i][l][r] = i번째 입력까지 밟고, 오른발이 r, 왼발이 l에 있을 때의 최소 비용

사실 i번째 입력을 밟았다는 사실이 l, r 중 하나가 i번째 입력에 있음을 의미한다.

따라서, 남은 한발만 저장하는 방식으로 조금 더 최적화를 할 수는 있지만 굳이 그럴 것 까지는 없어보여 진행하지 않았다.

점화식은 간단하게, 왼발로 온 경우, 오른 발로 온 경우를 나누어 구해주면 된다.

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int kMaxN = 100000;
const int kMaxCost = kMaxN * 5;

const int kCost[5][5] = { { 0, 2, 2, 2, 2 },
                          { kMaxCost, 1, 3, 4, 3 },
                          { kMaxCost, 3, 1, 3, 4 },
                          { kMaxCost, 4, 3, 1, 3 },
                          { kMaxCost, 3, 4, 3, 1 } };

vector<int> SEQUENCE;

int CACHE[kMaxN][5][5];

int Solve()
{
  CACHE[0][SEQUENCE[0]][0] = 2;
  CACHE[0][0][SEQUENCE[0]] = 2;

  for (size_t seq = 1; seq < SEQUENCE.size(); ++seq)
  {
    for (int lr = 0; lr < 25; ++lr)
    {
      const int l = lr / 5;
      const int r = lr % 5;

      if (SEQUENCE[seq] != l && SEQUENCE[seq] != r)
      {
        continue;
      }

      if (l == r)
      {
        continue;
      }

      for (int p = 0; p < 5; ++p)
      {
        if (SEQUENCE[seq] == l)
        {
          CACHE[seq][l][r] = min(CACHE[seq][l][r], CACHE[seq - 1][p][r] + kCost[p][l]);
        }
        else
        {
          CACHE[seq][l][r] = min(CACHE[seq][l][r], CACHE[seq - 1][l][p] + kCost[p][r]);
        }
      }
    }
  }

  int answer = kMaxCost;
  for (int left = 0; left < 5; ++left)
  {
    for (int right = 0; right < 5; ++right)
    {
      answer = min(answer, CACHE[SEQUENCE.size() - 1][left][right]);
    }
  }

  return answer;
}

int main(void)
{
  while (true)
  {
    int target;
    scanf(" %d", &target);

    if (target == 0)
    {
      break;
    }

    SEQUENCE.emplace_back(target);
  }

  for (int i = 0; i < kMaxN; ++i)
  {
    for (int j = 0; j < 5; ++j)
    {
      for (int k = 0; k < 5; ++k)
      {
        CACHE[i][j][k] = kMaxCost;
      }
    }
  }

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

  return 0;
}