[백준 2342] Dance Dance Revolution (C#, C++) - soo:bak

문제 링크

2342번 - Dance Dance Revolution

설명

DDR 게임에서 주어진 스텝을 순서대로 밟을 때 드는 최소 힘을 구하는 문제입니다.

발판은 중앙(0)과 상(1), 좌(2), 하(3), 우(4) 총 5개입니다. 이동 비용은 같은 위치 1, 중앙에서 이동 2, 인접 이동 3, 반대편 이동 4입니다. 두 발이 동시에 같은 위치에 있을 수 없습니다.

접근법

먼저 두 발의 위치를 상태로 하는 DP를 정의합니다. dp[left][right]는 왼발이 left, 오른발이 right에 있을 때까지의 최소 힘입니다.

다음으로 각 스텝마다 왼발 또는 오른발을 해당 위치로 이동시킵니다. 두 가지 선택 중 더 작은 비용을 선택하여 다음 상태로 전이합니다.

이후 모든 스텝을 처리한 뒤 가능한 모든 발 위치 조합 중 최솟값이 답이 됩니다.

시간 복잡도는 O(N)입니다.

Code

C#

using System;
using System.Collections.Generic;

namespace Solution {
  class Program {
    const int INF = int.MaxValue / 4;

    static int Cost(int from, int to) {
      if (from == to)
        return 1;
      if (from == 0)
        return 2;
      var diff = Math.Abs(from - to);
      if (diff == 2)
        return 4;
      return 3;
    }

    static void Main(string[] args) {
      var steps = new List<int>();
      var line = Console.ReadLine();
      if (line == null)
        return;
      var parts = line.Split();
      foreach (var p in parts) {
        var v = int.Parse(p);
        if (v == 0)
          break;
        steps.Add(v);
      }
      while (true) {
        var next = Console.ReadLine();
        if (next == null)
          break;
        foreach (var p in next.Split()) {
          var v = int.Parse(p);
          if (v == 0)
            break;
          steps.Add(v);
        }
        if (next.Contains("0"))
          break;
      }

      var dp = new int[5, 5];
      var ndp = new int[5, 5];
      for (var i = 0; i < 5; i++)
        for (var j = 0; j < 5; j++)
          dp[i, j] = INF;
      dp[0, 0] = 0;

      foreach (var s in steps) {
        for (var i = 0; i < 5; i++)
          for (var j = 0; j < 5; j++)
            ndp[i, j] = INF;

        for (var l = 0; l < 5; l++) {
          for (var r = 0; r < 5; r++) {
            if (dp[l, r] >= INF)
              continue;
            var c1 = dp[l, r] + Cost(l, s);
            if (c1 < ndp[s, r])
              ndp[s, r] = c1;

            var c2 = dp[l, r] + Cost(r, s);
            if (c2 < ndp[l, s])
              ndp[l, s] = c2;
          }
        }
        var temp = dp;
        dp = ndp;
        ndp = temp;
      }

      var ans = INF;
      for (var l = 0; l < 5; l++)
        for (var r = 0; r < 5; r++)
          if (dp[l, r] < ans)
            ans = dp[l, r];
      Console.WriteLine(ans);
    }
  }
}

C++

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

typedef vector<int> vi;

const int INF = 1e9;

int cost(int from, int to) {
  if (from == to)
    return 1;
  if (from == 0)
    return 2;
  int diff = abs(from - to);
  if (diff == 2)
    return 4;
  return 3;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  vi steps;
  int v;
  while (cin >> v) {
    if (v == 0)
      break;
    steps.push_back(v);
  }

  int dp[5][5], ndp[5][5];
  for (int i = 0; i < 5; i++)
    for (int j = 0; j < 5; j++)
      dp[i][j] = INF;
  dp[0][0] = 0;

  for (int s : steps) {
    for (int i = 0; i < 5; i++)
      for (int j = 0; j < 5; j++)
        ndp[i][j] = INF;

    for (int l = 0; l < 5; l++) {
      for (int r = 0; r < 5; r++) {
        if (dp[l][r] >= INF)
          continue;
        int c1 = dp[l][r] + cost(l, s);
        ndp[s][r] = min(ndp[s][r], c1);

        int c2 = dp[l][r] + cost(r, s);
        ndp[l][s] = min(ndp[l][s], c2);
      }
    }
    memcpy(dp, ndp, sizeof(dp));
  }

  int ans = INF;
  for (int l = 0; l < 5; l++)
    for (int r = 0; r < 5; r++)
      ans = min(ans, dp[l][r]);

  cout << ans << "\n";

  return 0;
}