[백준 2342] Dance Dance Revolution

문제

www.acmicpc.net/problem/2342

2342번: Dance Dance Revolution

 

풀이

현재 보고있는 지시사항에서 각 각의 발의 위치 상태에 따라 이동하는 비용이 전부 다르므로 상태를 정의하여 dp를 사용하면 해결할 수 있습니다.

---

1. "dp[cmd_idx][left][right] : 현재 보고 있는 지시사항의 인덱스(cmd_idx)에서 왼발의 위치가 left, 오른발의 위치가 right일 때, 모든 지시 사항을 만족하는 데 사용되는 최소의 힘"이라고 정의하면 $O(l*5^2)$내에 해결할 수 있습니다. (l = 지시사항의 길이)

 

2. 상태전이는 아래와 같습니다.

dp[idx][l][r] = min(dp[idx][l][r], dp[idx+1][l][r] + 1) (단, v[idx] = l or v[idx] = r)

                  = min(dp[idx][l][r], dp[idx+1][v[idx]][r] + 2 or dp[idx + 1][l][v[idx]] + 2)  (단, l = 0 or r = 0) 

                  = min(dp[idx][l][r], dp[idx+1][v[idx]][r] + 4 or dp[idx + 1][l][v[idx]] + 4)  (단, v[idx]와 l or r이 반대편)

                  = min(dp[idx][l][r], dp[idx+1][v[idx]][r] + 3 or dp[idx + 1][l][v[idx]] + 3)  (단, v[idx]와 l or r이 인접)

 

코드

#include <bits/stdc++.h>
using namespace std;

const int inf = 0x3f3f3f3f;
int n, ipt, dp[100001][5][5];
vector<int> v;

int go(int idx, int l, int r) {
	if (l && r && l == r) return inf;
	if (idx == n) return 0;
	int &ret = dp[idx][l][r];
	if (ret != -1) return ret;
	ret = inf;
	int target = v[idx];
	if (target == l || target == r) ret = min(ret, go(idx + 1, l, r) + 1);
	if (l == 0) ret = min(ret, go(idx + 1, target, r) + 2);
	if (r == 0) ret = min(ret, go(idx + 1, l, target) + 2);
	if (l) ret = min(ret, go(idx + 1, target, r) + (abs(target - l) == 2 ? 4 : 3));
	if (r) ret = min(ret, go(idx + 1, l, target) + (abs(target - r) == 2 ? 4 : 3));
	return ret;
}

int main() {
	cin.tie(NULL); cout.tie(NULL);
	ios_base::sync_with_stdio(false);
	memset(dp, -1, sizeof(dp));

	while (1) {
		cin >> ipt;
		if (!ipt) break;
		v.emplace_back(ipt);
	}
	n = v.size();
	cout << go(0, 0, 0);
}