Dance Dance Revolution

#include <iostream> #include <vector> #include <algorithm> #define INF 987654321 #define MAXX 100001 using namespace std; typedef pair<int, int> pp; int direc[MAXX] = { 0 }; int idx = 0; int dp[MAXX][5][5]; int move(int now, int prev) { if (!prev) return 2; else if (now == prev) return 1; else if (abs(now - prev)==2) return 4; else return 3; } int dfs(int cnt, int left, int right) { if (cnt == idx) { int lRes = move(direc[cnt], left); int rRes = move(direc[cnt], right); return min(lRes, rRes); } if (dp[cnt][left][right] != INF) return dp[cnt][left][right]; int& ret = dp[cnt][left][right]; //명령에따라서 최소값을 구한다. //왼발 혹은 오른발을 움직여서 최소 움직임을 구한다. /* 0-> 다른 지점 : power 2 다른 지점- > 다른지점 if 반대방향일 때 : power 4 else power 3 같은 지점 -> 같은 지점 : power 1 */ int lRes = move(direc[cnt], left); int rRes = move(direc[cnt], right); ret = min(ret, min(lRes+ dfs(cnt + 1, direc[cnt], right), rRes+ dfs(cnt + 1, left, direc[cnt]))); return ret; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); while (1) { int n; cin >> n; if (n == 0) break; direc[++idx] = n; } //두 발이 있음 (두 발은 동시에 움직이지 않고, 같은 지점에 같이 있으면 안된다. 처음에는 0,0에 같이 있음) //dp[][][] - > k번째 지시사항에서 왼쪽발 혹은 오른쪽 발이 움직였을 때의 최소 힘의 값 for (int i = 1; i <=idx; i++) { for (int j = 0; j <= 4; j++) { for (int k = 0; k <= 4; k++) { dp[i][j][k] = INF; } } } dp[0][0][0] = 0; cout << dfs(1, 0, 0) << '\n'; return 0; }