2342번 Dance Dance Revolution

Posted Aug 10, 2025

By matin1202

13 min read

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

풀이

2342번 Dance Dance Revolution 문제는 주어진 발판 순서에 따라 DDR 게임을 플레이할 때, 최소한의 힘(비용)으로 모든 발판을 밟는 방법을 찾는 문제입니다. 두 발은 동시에 움직일 수 없으며, 각 발판을 밟는 데 드는 힘은 현재 발의 위치와 다음에 밟을 발판의 위치에 따라 달라집니다. 이 문제는 전형적인 동적 계획법(Dynamic Programming) 문제로 해결할 수 있습니다.

동적 계획법 접근 방식:

이 문제의 핵심은 현재 어떤 발판을 밟아야 하는지 뿐만 아니라, 두 발이 현재 어디에 위치해 있는지가 다음 동작의 비용에 영향을 미친다는 점입니다. 따라서 DP 상태를 두 발의 위치를 포함하여 정의해야 합니다.

상태 정의: 이 문제에서 DP 상태는 dp[왼쪽_발_위치][오른쪽_발_위치]로 정의할 수 있습니다. 이는 해당 발 위치에 도달하기까지의 최소 총 힘을 나타냅니다. 발판의 번호는 다음과 같습니다:
- 0: 중앙
- 1: 상
- 2: 좌
- 3: 하
- 4: 우
발판 순서의 길이가 최대 10만 개이므로, 모든 스텝을 DP 테이블의 차원으로 사용하는 것은 메모리 초과를 유발합니다. 대신, 현재 처리 중인 발판(target)을 기준으로 이전 상태와 다음 상태를 구분하는 롤링 배열(Rolling Array) 기법을 사용합니다. 즉, dp 테이블은 dp[5][5] 크기를 유지하며, 매 스텝마다 next_dp를 계산한 후 dp로 업데이트하는 방식입니다.
비용 함수: cost(from, to) 함수는 from 발판에서 to 발판으로 발을 이동하는 데 드는 힘을 계산합니다.
- from과 to가 같은 위치인 경우: 1 (발을 움직이지 않고 유지)
- from이 0 (중앙)인 경우: 2 (중앙에서 다른 발판으로 이동)
- from에서 to로 이동할 때, from과 to가 마주보는 발판인 경우 (예: 1<->3, 2<->4): 4
- 그 외의 경우 (인접한 발판으로 이동): 3
이 비용 함수는 constexpr로 정의되어 컴파일 시간에 계산되도록 최적화될 수 있습니다.
초기 상태: dp[0][0] = 0으로 초기화합니다. 이는 게임 시작 시 두 발 모두 중앙(0)에 있으며, 이때까지 든 힘은 0임을 의미합니다. 나머지 dp 값은 INT_MAX (도달 불가능한 상태)로 초기화합니다.
전이 규칙: 입력으로 주어지는 발판 순서 steps의 각 target에 대해 다음을 반복합니다.
- 매 스텝 시작 시 next_dp 테이블은 INT_MAX로 초기화합니다.
- 현재 dp 테이블의 모든 (l, r) 쌍(l: 왼쪽 발 위치, r: 오른쪽 발 위치)을 순회합니다.
- dp[l][r]이 INT_MAX가 아니라면 (도달 가능한 상태라면):
  1. 왼쪽 발이 target을 밟는 경우: 오른쪽 발은 r에 그대로 있습니다. (target이 r과 같지 않아야 함: 발이 겹치면 안 됨) next_dp[target][r] = min(next_dp[target][r], dp[l][r] + cost(l, target));
  2. 오른쪽 발이 target을 밟는 경우: 왼쪽 발은 l에 그대로 있습니다. (target이 l과 같지 않아야 함: 발이 겹치면 안 됨) next_dp[l][target] = min(next_dp[l][target], dp[l][r] + cost(r, target));
- 하나의 스텝이 끝나면, dp = next_dp;로 dp 테이블을 업데이트합니다.
결과: 모든 발판을 처리한 후, 최종 dp 테이블에서 모든 가능한 (l, r) 발 위치 조합 중 최소 힘을 찾습니다. min(dp[l][r])이 최종 답이 됩니다.

시간 복잡도: 이 문제의 DP 상태는 dp[왼쪽_발_위치][오른쪽_발_위치]로 정의됩니다. 각 발이 가질 수 있는 위치는 5가지(중앙, 상, 좌, 하, 우)이므로, 각 스텝에서 DP 테이블의 크기는 $5 \times 5 = 25$입니다. 입력으로 주어지는 발판 순서의 길이를 $L$이라고 할 때, 각 발판 스텝마다 25가지의 이전 상태를 순회하며 상수 시간의 연산을 수행합니다. 따라서 전체 시간 복잡도는 $O(L \times 25) = O(L)$이 됩니다.

공간 복잡도: 롤링 배열 기법을 사용하여 현재 스텝의 dp 테이블과 다음 스텝의 next_dp 테이블만을 메모리에 유지합니다. 각 테이블의 크기는 $5 \times 5$이므로, 총 공간 복잡도는 $O(5 \times 5) = O(1)$로 상수 공간을 사용합니다.

코드

2342.cpp

#include <bits/stdc++.h>
using namespace std;
constexpr int cost(int start, int end){
    if(start == end) return 1;
    if(start == 0) return 2;
    if(abs(start-end) == 2) return 4;
    return 3;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    queue<int> step;
    while(true){
        cin >> t;
        if(t == 0)
            break;
        step.push(t);
    }
    auto dp = vector(5, vector(5, INT_MAX));
    dp[0][0] = 0;
    int prev = 0;
    while(!step.empty()){
        int target = step.front();
        step.pop();
        auto next = vector(5, vector(5, INT_MAX));
        for(int i = 0;i < 5;i++){
            if(dp[prev][i] != INT_MAX){
                if(target != i){
                    next[target][i] = min(next[target][i], dp[prev][i] + cost(prev, target));
                }
                if(target != prev){
                    next[prev][target] = min(next[prev][target], dp[prev][i] + cost(i, target));
                }
            }
            if(dp[i][prev] != INT_MAX){
                if(target != i){
                    next[i][target] = min(next[i][target], dp[i][prev] + cost(prev, target));
                }
                if(target != prev){
                    next[target][prev] = min(next[target][prev], dp[i][prev] + cost(i, target));
                }
            }
        }
        dp = move(next);
        prev = target;
    }
    int ans = INT_MAX;
    for(int i = 0;i < 5;i++){
        ans = min(ans, dp[prev][i]);
        ans = min(ans, dp[i][prev]);
    }
    cout << ans << '\n';
    return 0;
}

Standard Input (stdin):

C++

최적화

기존 2342.cpp의 전이 방식 (명시적인 l, r 순회): 2342.cpp에서는 매 스텝마다 for(int l = 0; l < 5; l++) { for(int r = 0; r < 5; r++) { ... } }와 같이 이전 상태 dp[l][r]의 모든 25가지 경우의 수를 직접 순회하며 다음 상태를 계산합니다. 이는 정확하지만, 현재 스텝의 target 발판을 밟고 나면 두 발 중 하나는 반드시 target 위치에 있게 된다는 문제의 특성을 충분히 활용하지 못합니다.

2342_optimize.cpp의 최적화된 전이 방식 (prev 활용): 2342_optimize.cpp는 이 특성을 활용하여, 이전 스텝에서 밟았던 발판의 위치를 prev 변수로 추적합니다. 그리고 다음 스텝의 dp 테이블을 계산할 때, 단순히 모든 (l, r) 조합을 순회하는 대신, 이전 스텝에서 prev가 아닌 다른 발 (i)이 어떤 위치에 있었는지에만 집중합니다.

구체적으로, dp[curr][prev][i] 또는 dp[curr][i][prev] 형태의 상태만 고려하여 다음 target 발판으로 이동하는 비용을 갱신합니다. 이는 다음과 같은 로직으로 구현됩니다:

  
// dp[curr]는 이전 스텝의 결과를 담고 있음
// prev는 이전 스텝에서 밟았던 target 발판의 위치
for(int i = 0; i < 5; i++){
    // 경우 1: 왼쪽 발이 이전 스텝의 target (prev)에 있고, 오른쪽 발이 i에 있던 상태
    if(dp[curr][prev][i] != INT_MAX){
        // 왼쪽 발이 현재 target을 밟는 경우 (오른쪽 발은 i에 그대로)
        if(target != i) {
            dp[next][target][i] = min(dp[next][target][i], dp[curr][prev][i] + cost(prev, target));
        }
        // 오른쪽 발이 현재 target을 밟는 경우 (왼쪽 발은 prev에 그대로)
        if(target != prev) {
            dp[next][prev][target] = min(dp[next][prev][target], dp[curr][prev][i] + cost(i, target));
        }
    }

    // 경우 2: 왼쪽 발이 i에 있고, 오른쪽 발이 이전 스텝의 target (prev)에 있던 상태
    if(dp[curr][i][prev] != INT_MAX){
        // 왼쪽 발이 현재 target을 밟는 경우 (오른쪽 발은 prev에 그대로)
        if(target != i) {
            dp[next][i][target] = min(dp[next][i][target], dp[curr][i][prev] + cost(i, target));
        }
        // 오른쪽 발이 현재 target을 밟는 경우 (왼쪽 발은 i에 그대로)
        if(target != prev) {
            dp[next][target][prev] = min(dp[next][target][prev], dp[curr][i][prev] + cost(prev, target));
        }
    }
}

이러한 방식은 이전 스텝에서 유효했던 5x5가지의 모든 상태를 순회하는 대신, prev 위치를 고정하고 나머지 한 발의 위치 i만 순회하므로, 실제로 연산을 수행하는 DP 상태 전이의 수를 줄여 성능 향상을 기대할 수 있습니다. 즉, 매 스텝마다 이전 발판을 밟은 이후의 유효한 발 위치 조합이 제한적이라는 점을 활용하는 것입니다.

최적화된 코드

2342_optimize.cpp

#include <bits/stdc++.h>
using namespace std;
constexpr int cost(int start, int end){
    if(start == end) return 1;
    if(start == 0) return 2;
    if(abs(start-end) == 2) return 4;
    return 3;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    queue<int> step;
    while(true){
        cin >> t;
        if(t == 0)
            break;
        step.push(t);
    }
    vector<vector<int>> dp[2];
    dp[0].assign(5, vector<int>(5, INT_MAX));
    dp[1].assign(5, vector<int>(5, INT_MAX));
    int curr = 0, next = 1;
    dp[curr][0][0] = 0;
    int prev = 0;
    while(!step.empty()){
        int target = step.front();
        step.pop();
        dp[next].assign(5, vector<int>(5, INT_MAX));
        for(int i = 0;i < 5;i++){
            if(dp[curr][prev][i] != INT_MAX){
                if(target != i){
                    dp[next][target][i] = min(dp[next][target][i], dp[curr][prev][i] + cost(prev, target));
                }
                if(target != prev){
                    dp[next][prev][target] = min(dp[next][prev][target], dp[curr][prev][i] + cost(i, target));
                }
            }
            if(dp[curr][i][prev] != INT_MAX){
                if(target != i){
                    dp[next][i][target] = min(dp[next][i][target], dp[curr][i][prev] + cost(prev, target));
                }
                if(target != prev){
                    dp[next][target][prev] = min(dp[next][target][prev], dp[curr][i][prev] + cost(i, target));
                }
            }
        }
        swap(curr, next);
        prev = target;
    }
    int ans = INT_MAX;
    for(int i = 0;i < 5;i++){
        ans = min(ans, dp[curr][prev][i]);
        ans = min(ans, dp[curr][i][prev]);
    }
    cout << ans << '\n';
    return 0;
}

Standard Input (stdin):

C++

BaekJoon

This post is licensed under CC BY 4.0 by the author.

풀이

코드

최적화

최적화된 코드

Trending Tags