백준 2342번 Dance Dance Revolution C++

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

 

상당히 어려운 dp문제였다. cache[ i ][ j ][ k ] 를 i번째 지시사항에서 왼쪽발은 j, 오른쪽발은 k일때의 값으로 하고 풀었다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

const int INF = 0x3fffffff;

int cnt = 0;

int power[5][5] = {
  {INF,2,2,2,2},
  {INF,1,3,4,3},
  {INF,3,1,3,4},
  {INF,4,3,1,3},
  {INF,3,4,3,1},
};

vector<vector<vector<int>>> cache;
vector<int> orders;

int GetPower(int cnt, int left, int right) {

    if (cnt == 0) {
        if (left == 0 && right == 0)
            return 0;
        else return INF;
    }

    int &ret = cache[cnt][left][right];
    if (ret != -1)
        return ret;

    ret = INF;

    if (orders[cnt] != left && orders[cnt] != right)
        return ret;

    for (int i = 0; i < 5; i++) {
        if (power[i][left] != INF) {
            int lastPower = GetPower(cnt - 1, i, right);
            if (lastPower != INF) {
                ret = min(ret, lastPower + power[i][left]);
            }
        }
        if (power[i][right] != INF) {
            int lastPower = GetPower(cnt - 1, left, i);
            if (lastPower != INF) {
                ret = min(ret, lastPower + power[i][right]);
            }
        }
    }

    return ret;
}

void Init() {
    cache = vector<vector<vector<int>>>(cnt + 1, vector<vector<int>>(5, vector<int>(5, -1)));
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            cache[0][i][j] = INF;
        }
    }
    for (int i = 1; i <= cnt; i++) {
        cache[i][0][0] = INF;
        cache[i][1][1] = INF;
        cache[i][2][2] = INF;
        cache[i][3][3] = INF;
        cache[i][4][4] = INF;
    }
    cache[0][0][0] = 0;
}

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

    int ans = INF;

    orders.push_back(0);

    while (true) {
        int order;
        cin >> order;
        if (order == 0) break;
        orders.push_back(order);
        cnt++;
    }

    if (cnt == 0) {
        cout << 0;
        return 0;
    }

    Init();

    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            ans = min(ans, GetPower(cnt, i, j));
        }
    }

    cout << ans;
}