[백준 2342] Dance Dance Revolution

 

 DP 문제이다. 순수한 브루트 포스는 O(2^n)에 해당하기 때문에 문제를 풀 수 없다. 처음엔 그리디를 이용할까 했으나, 1 4 3 4 와 같은 케이스서는 최적해를 보장할 수 없기 때문에 택할 수 없었다. 결국에는 모든 경우에 대해서 탐색을 진행해야 하는 케이스이며, 나는 DP를 이용하기로 했다.

 지시 사항을 하나씩 순회하며, 이전의 발 상태 및 비용 값들로부터 발을 옮기는 케이스들을 하나씩 계산해 DP 테이블을 채우면 되겠다는 생각이 들었다. 지시 사항이 100,000개를 넘지 않고, 처음을 제외하곤 각 발판에 발이 하나씩만 놓일 수 있으므로 발판에 발을 둔 상태를 비트마스크로 표현한다면 5bit면 충분하다. 따라서 DP 테이블은 최대 2^5 * 100,000인 int 테이블이 되고, 시간 복잡도와 공간 복잡도 모두 문제 없다.

 

 점화식은 위에도 쓴 것처럼 이전 단계의 발 상태 및 최소비용 값들을 모두 확인하여, 거기서 파생될 수 있는 이번 단계의 발 상태 및 최소비용 값들을 생성해 주는 것이다. 이전의 발 상태를 보고, 각각의 두 발로 이번에 밟아야 할 발판으로 발을 옮겼을 때의 상태와 그때의 최소비용을 갱신해 주면 된다.

 나는 각 발판의 비트마스크 내 위치를 1을 0~4만큼 left shift 한 위치로 설정했다. 그렇기 때문에 당연히 1<<0 .. 1<<4까지 순회하면서 AND 연산을 하면 해당 발판을 밟고 있는지 여부를 알 수 있다. 그리고 밟고 있던 발로 새로 밟아야 할 발판을 밟은 상태를 만드는 부분은 기존의 발 상태와 움직이려는 발판 비트를 XOR해서 반대 발만 남은 상태로 바꾸고, 새로 밟으려는 발판 비트를 OR 연산해 줘서 밟음 처리해주었다. 

 이 과정에서 새로 밟으려는 위치가 반대 발이 밟고 있는 발판인 경우는 제외처리 해주었다. 만약 반대 발이 밟고 있던 위치를 밟은 경우에는 새로 만든 발의 상태가 밟으려는 발판 비트 값과 같을 것이기 때문에, 이에 해당하지 않는 경우에만 DP 테이블을 갱신하도록 했다.

 초기값은 첫 지시 사항에 맞춰 발 하나를 옮긴 발 상태일 수밖에 없으므로, 그 상태에 해당하는 DP행을 찾아 0번째 열에 최소 비용을 2로 주고 시작하면 된다.

 

 모든 탐색이 끝나고 나면, DP 테이블 내에서 마지막 지시 사항까지 이행한 경우가 있는 줄을 택해(나 같은 경우에는 지시 사항 리스트의 길이-1 번째 열이다) 최솟값을 확인해 출력해 주면 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 987654321

using namespace std;

int getMoveCost(int start, int end) {
    if(start==0) {
        return 2;
    } else if(start==end) {
        return 1;
    } else if(start%2==end%2) {
        return 4;
    } else {
        return 3;
    }
}

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

    int n;
    vector<int> ddrNumList;

    cin >> n;

    while(n!=0) {
        ddrNumList.push_back(n);
        cin >> n;
    }

    if(ddrNumList.empty()) {
        cout << "0";
        return 0;
    }

    vector<vector<int> > dp(32, vector<int>(ddrNumList.size(), INF));
    dp[1<<ddrNumList[0] | 1][0] = 2;

    for(int i=1; i<ddrNumList.size(); i++) {
        for(int j=0; j<32; j++) {
            if(dp[j][i-1]!=INF) {
                for(int k=0; k<5; k++) {
                    if(1<<k & j) {
                        int nextPosition = j ^ 1<<k | 1<<ddrNumList[i];
                        if(nextPosition != 1<<ddrNumList[i]) {
                            dp[nextPosition][i] = min(dp[nextPosition][i], dp[j][i-1] + getMoveCost(k, ddrNumList[i]));
                        }
                    }
                }
            }
        }
    }

    int minCost = INF;
    for(int i=0; i<32; i++) {
        minCost = min(minCost, dp[i][ddrNumList.size()-1]);
    }

    cout << minCost;
}