2342번 : Dance Dance Revolution [C++]

문제 링크

성공 여부(걸린 시간): 깔끔하지 못한 성공 (1시간 30분)

아이디어

처음에 문제를 제대로 안 읽고 0번 위치에서 다른 칸으로 이동하는 비용을 3으로 잡아버리는 실수를 했다.
이 상태에서도 예제 테스트케이스는 전부 통과해서, 무엇이 잘못되었는지 한참을 헤맸다.

이 문제는 기본적으로 이전 단계의 발 위치 상태를 유지하면서 다음 칸을 누르는 최소 비용을 누적해 나가는 DP 문제이다.

내가 사용한 아이디어는 다음과 같다.

• dp[i][l][r]
  → i번째로 눌러야 할 칸까지 처리했을 때
  → 왼발이 l, 오른발이 r에 있을 때의 최소 힘

i번째 칸을 누를 때,

• i-1번째까지의 상태에서
  • 왼발이 움직여서 i번째 칸을 누르는 경우
  • 오른발이 움직여서 i번째 칸을 누르는 경우
    를 각각 고려한다.

또, 한 발이 움직일 때 다른 한 발은 그대로 유지된 상태이기 때문에,
남아있는 발의 위치에 따라 가능한 모든 경우를 순회하면서 DP를 갱신하도록 구성하였다.

초기에는 (0, 0) 상태에서 시작해야 하므로,
첫 입력에 대해서는 직접 초기 상태를 만들어 주어야 DP가 정상적으로 시작된다.

풀이 코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;

int dp[100001][5][5];
int cost[5][5] = {
    {0, 2, 2, 2, 2},
    {2, 1, 3, 4, 3},
    {2, 3, 1, 3, 4},
    {2, 4, 3, 1, 3},
    {2, 3, 4, 3, 1}
};

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

    int num;
    vector<int> v;
    v.push_back(0);
    cin >> num;
    v.push_back(num);
    while (num != 0) {
        cin >> num;
        if (num == 0) break;
        v.push_back(num);
    }

    int N = v.size() - 1;
    memset(dp, 0x7f7f7f7f, sizeof(dp));

    // 시작 상태 (0, 0)에서 첫 입력을 밟는 경우
    dp[1][v[1]][0] = 2;
    dp[1][0][v[1]] = 2;

    for (int i = 1; i <= N; i++) {
        for (int other = 0; other <= 4; other++) {

            // 이전에 누른 발을 다시 움직이는 경우
            if (v[i - 1] != other && other != v[i]) {
                // 왼발 이동
                dp[i][v[i]][other] = min(
                    dp[i - 1][v[i - 1]][other] + cost[v[i - 1]][v[i]],
                    dp[i][v[i]][other]
                );
                // 오른발 이동
                dp[i][other][v[i]] = min(
                    dp[i - 1][other][v[i - 1]] + cost[v[i - 1]][v[i]],
                    dp[i][other][v[i]]
                );
            }

            // 다른 발이 이전 칸을 밟고 남은 발로 i번째 칸을 누르는 경우
            if (v[i - 1] != v[i] && other != v[i - 1]) {
                // 왼발 이동
                dp[i][v[i]][v[i - 1]] = min(
                    dp[i - 1][other][v[i - 1]] + cost[other][v[i]],
                    dp[i][v[i]][v[i - 1]]
                );
                // 오른발 이동
                dp[i][v[i - 1]][v[i]] = min(
                    dp[i - 1][v[i - 1]][other] + cost[other][v[i]],
                    dp[i][v[i - 1]][v[i]]
                );
            }
        }
    }

    int answer = 0x7f7f7f7f;
    for (int left = 0; left <= 4; left++) {
        for (int right = 0; right <= 4; right++) {
            answer = min(dp[N][left][right], answer);
        }
    }

    cout << answer;
    return 0;
}