[백준/C++] 2342번: Dance Dance Revolution

문제

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

---

문제 요약

DDR(Dance Dance Revolution)은 아래와 같은 모양의 발판 위에서 주어진 스텝에 맞춰 나가는 게임이다.

 

편의상 중점을 0, 위를 1, 왼쪽을 2, 아래를 3, 오른쪽을 4라고 정한다.

 

게이머는 두 발을 중앙에 모으고 게임을 시작하면 지시에 따라 왼쪽 또는 오른쪽 발을 움직인다.(두 발이 동시에 움직이지는 않는다.)

 

두 발이 같은 지점에 있는 것이 허락되지 않는다.

 

발이 움직이는 위치에 따라서 드는 힘이 다르다.

 

1. 중앙에 있던 발이 다른 지점으로 움직이면, 2의 힘을 사용한다.

2. 다른 지점에서 인접한 지점으로 움직이면, 3의 힘을 사용한다.

3. 반대편으로 발을 움직이면, 4의 힘을 사용한다.

4. 같은 지점을 한 번 더 누른다면, 1의 힘을 사용한다.

 

모든 지시 사항을 만족하는 데 사용하는 최소 힘을 출력한다.

---

코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <tuple>
#include <queue>

#define INF 1e9

using namespace std;

vector<int> v;

// cost[i][j]: i에서 j로 이동 시 비용
int cost[5][5] = {{1, 2, 2, 2, 2}, {0, 1, 3, 4, 3}, {0, 3, 1, 3, 4}, {0, 4, 3, 1, 3}, {0, 3, 4, 3, 1}};

int dp[100010][5][5];

// step번째 단계에서 왼쪽 발이 left 발판을, 오른쪽 발이 right 발판을 밟고 있을 때까지 최소 비용 
int dfs(int step, int left, int right) {
    // 종료 조건
    if (step == v.size()) return 0;

    // 0이 아닌 발판에 같은 발이 있는 경우 (큰 수를 반환하여 min 연산 시 해당 경우 탐색을 제한)
    if ((left != 0 && right != 0) && left == right) return INF;

    // 이미 구했다면
    if (dp[step][left][right] != -1) {
        return dp[step][left][right];
    }

    return dp[step][left][right] = min(
        dfs(step + 1, v[step], right) + cost[left][v[step]], 
        dfs(step + 1, left, v[step]) + cost[right][v[step]]);
}

int main() {
    // 입력
    while (true) {
        int num;
        cin >> num;

        if (num == 0) {
            break;
        }

        v.push_back(num);
    }

    memset(dp, -1, sizeof(dp));

    cout << dfs(0, 0, 0);

    return 0;
}

// 1 3 2 4 1 2 0

---

코드 설명

3차원 Dynamic Programming을 통해 문제를 해결한다.

 

cost[i][j]는 i에서 j로 이동하는 데 드는 비용이다.

 

메모이제이션 dp[i][j][k]는 i번 단계까지 왼쪽 발이 발판 j를 오른쪽 발이 발판 k를 밟았을 때, 최소 비용이다.

 

다음 단계를 재귀적으로 호출하여 왼발을 움직일 경우와 오른발을 움직일 경우 중 최소 비용을 계산하고 저장한 후 반환한다.