백준 2342 - Dance Dance Revolution

문제 설명

승환이는 요즘 "Dance Dance Revolution"이라는 게임에 빠져 살고 있다. 하지만 그의 춤 솜씨를 보면 알 수 있듯이, 그는 DDR을 잘 하지 못한다. 그럼에도 불구하고 그는 살을 뺄 수 있다는 일념으로 DDR을 즐긴다.

DDR은 아래의 그림과 같은 모양의 발판이 있고, 주어진 스텝에 맞춰 나가는 게임이다. 발판은 하나의 중점을 기준으로 위, 아래, 왼쪽, 오른쪽으로 연결되어 있다. 편의상 중점을 0, 위를 1, 왼쪽을 2, 아래를 3, 오른쪽을 4라고 정하자.

처음에 게이머는 두 발을 중앙에 모으고 있다.(그림에서 0의 위치) 그리고 게임이 시작하면, 지시에 따라 왼쪽 또는 오른쪽 발을 움직인다. 하지만 그의 두 발이 동시에 움직이지는 않는다.

이 게임에는 이상한 규칙이 더 있다. 두 발이 같은 지점에 있는 것이 허락되지 않는 것이다. (물론 게임 시작시에는 예외이다) 만약, 한 발이 1의 위치에 있고, 다른 한 발이 3의 위치에 있을 때, 3을 연속으로 눌러야 한다면, 3의 위치에 있는 발로 반복해야 눌러야 한다는 것이다.

오랫동안 DDR을 해 온 백승환은 발이 움직이는 위치에 따라서 드는 힘이 다르다는 것을 알게 되었다. 만약, 중앙에 있던 발이 다른 지점으로 움직일 때, 2의 힘을 사용하게 된다. 그리고 다른 지점에서 인접한 지점으로 움직일 때는 3의 힘을 사용하게 된다. (예를 들면 왼쪽에서 위나 아래로 이동할 때의 이야기이다.) 그리고 반대편으로 움직일때는 4의 힘을 사용하게 된다. (위쪽에서 아래쪽으로, 또는 오른쪽에서 왼쪽으로). 만약 같은 지점을 한번 더 누른다면, 그때는 1의 힘을 사용하게 된다.

만약 1 → 2 → 2 → 4를 눌러야 한다고 가정해 보자. 당신의 두 발은 처음에 (point 0, point 0)에 위치하여 있을 것이다. 그리고 (0, 0) → (0, 1) → (2, 1) → (2, 1) → (2, 4)로 이동하면, 당신은 8의 힘을 사용하게 된다. 다른 방법으로 발을 움직이려고 해도, 당신은 8의 힘보다 더 적게 힘을 사용해서 1 → 2 → 2 → 4를 누를 수는 없을 것이다.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 주어지는 숫자의 발판을 밟는데 드는 비용을 최소로 만드는 것이다.

두 발은 중앙에 모인 채로 시작하며 중앙에서 다른 발판으로 갈 때 2, 인접한 발판들끼리는 3, 반대 발판으로는 4의 비용이 든다.

 

해당 문제는 dp로 풀 수 있다.

양발을 사용하기 때문에 조금 생각하기 까다로운 문제이다.

양발을 pair로 표현하여 key로 사용하는 map을 통해 메모이제이션을 진행했다.

{0,0}, {0,1}, {0,2},... {4,4} 이렇게 양발이 어느 위치에 있는지 나타내는 것이다.

이 key로 j번째 발판을 밟았을 경우의 최소비용을 메모하면 된다.

단, 이전 단계의 비용을 가져와야 하기 때문에 가상의 단계(초기화)를 추가하여 진행하는 것이 편하다.

 

비용을 갱신하는 규칙은 현재 밟아야 하는 발판을 밟을 수 있는 경우에서 +a를 하는 것이다.

예를 들어, 현재 2번 발판을 밟아야 한다.

그렇다면 이 발판 밟는다면 왼발이 0, 1, 3, 4에 있어야 하며 오른발도 마찬가지이다.

즉, 이번 발이 0에 있었다면 +2를, 1,3에 있었다면 +3, 4에 있었다면 +4를 계산하여 최솟값을 기록하면 된다.

오른발도 마찬가지로 하면 된다.

한 가지 주의할 점은 같은 발판을 연속으로 밟는 경우이다.

한 단계에 하나의 발만 움직일 수 있기 때문에 같은 발판을 밟으려면 왼발과 오른발 중 하나가 현재 밟아야 하는 발판을 밟고 있는 경우이다.

따라서, 왼발과 오른발을 l, r로 표현한다면 다음과 같이 계산할 수 있다.

dp[{l, r}][j] = min(dp[foots][j], dp[{l, r}][j - 1] + 1);

 

이후, 마지막 단계에 기록된 최솟값을 찾으면 된다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9

using namespace std;

vector<int> opers;
map<pair<int, int>, vector<int>> dp;
vector<int> idxMap;
const int MAX = 987654321;

vector<int> GetNear(int a)
{
    vector<int> result;

    if (a == 4)
    {
        result.push_back(1);
        result.push_back(3);
    }
    else if(a == 1)
    {
        result.push_back(2);
        result.push_back(4);
    }
    else
    {
        result.push_back(a + 1);
        result.push_back(a - 1);
    }

    return result;
}

int GetOpposite(int a)
{
    if (a == 1) return 3;
    if (a == 2) return 4;
    if (a == 3) return 1;
    if (a == 4) return 2;
}


int main() 
{
    INPUT_OPTIMIZE;

    opers.push_back(-1);

    while (true)
    {
        int d;
        cin >> d;

        if (d == 0) break;

        opers.push_back(d);
    }

    if (opers.size() == 1)
    {
        cout << 0;
        return 0;
    }

    for (int i = 0; i < 5; i++)
    {
        for (int j = 0; j < 5; j++)
        {
            dp[{i, j}].resize(opers.size(), MAX);
        }
    }

    //초기화
    dp[{0, 0}][0] = 0;

    for (int j = 1; j < opers.size(); j++)
    {
        for (auto& [foots, cost] : dp)
        {
            int l = foots.first;
            int r = foots.second;

            if (l == opers[j])
            {
                //같은 발
                dp[foots][j] = min(dp[foots][j], dp[{l, r}][j - 1] + 1);

                //왼발 옮기기
                {
                    //중앙에서 옮기기
                    dp[foots][j] = min(dp[foots][j], dp[{0, r}][j - 1] + 2);

                    //인접한 칸 옮기기(2개)
                    auto near = GetNear(l);
                    if (near[0] != r)
                    {
                        dp[foots][j] = min(dp[foots][j], dp[{near[0], r}][j - 1] + 3);
                    }
                    if (near[1] != r)
                    {
                        dp[foots][j] = min(dp[foots][j], dp[{near[1], r}][j - 1] + 3);
                    }

                    //반대 칸 옮기기
                    if (GetOpposite(l))
                    {
                        dp[foots][j] = min(dp[foots][j], dp[{GetOpposite(l), r}][j - 1] + 4);
                    }
                }
            }
            else if (r == opers[j])
            {
                //같은 발
                dp[foots][j] = min(dp[foots][j], dp[{l, r}][j - 1] + 1);

                //오른발 옮기기
                {
                    //중앙에서 옮기기
                    dp[foots][j] = min(dp[foots][j], dp[{l, 0}][j - 1] + 2);

                    //인접한 칸 옮기기(2개)
                    auto near = GetNear(r);
                    if (near[0] != l)
                    {
                        dp[foots][j] = min(dp[foots][j], dp[{l, near[0]}][j - 1] + 3);
                    }
                    if (near[1] != l)
                    {
                        dp[foots][j] = min(dp[foots][j], dp[{l, near[1]}][j - 1] + 3);
                    }

                    //반대 칸 옮기기
                    if (GetOpposite(r))
                    {
                        dp[foots][j] = min(dp[foots][j], dp[{l, GetOpposite(r)}][j - 1] + 4);
                    }
                }
            }
        }
    }

    int ans = INT_MAX;
    for (auto& [foots, cost] : dp)
    {
        if (foots.first == 0 && foots.second == 0) continue;
        ans = min(ans, cost[opers.size() - 1]);
    }

    cout << ans;

    return 0;
}

---