[C/C++] 백준 - 2342번 : Dance Dance Revolution

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

2342번: Dance Dance Revolution

문제

승환이는 요즘 "Dance Dance Revolution"이라는 게임에 빠져 살고 있다. 하지만 그의 춤 솜씨를 보면 알 수 있듯이, 그는 DDR을 잘 하지 못한다. 그럼에도 불구하고 그는 살을 뺄 수 있다는 일념으로 DDR을 즐긴다.

DDR은 아래의 그림과 같은 모양의 발판이 있고, 주어진 스텝에 맞춰 나가는 게임이다. 발판은 하나의 중점을 기준으로 위, 아래, 왼쪽, 오른쪽으로 연결되어 있다. 편의상 중점을 0, 위를 1, 왼쪽을 2, 아래를 3, 오른쪽을 4라고 정하자.

처음에 게이머는 두 발을 중앙에 모으고 있다.(그림에서 0의 위치) 그리고 게임이 시작하면, 지시에 따라 왼쪽 또는 오른쪽 발을 움직인다. 하지만 그의 두 발이 동시에 움직이지는 않는다.

이 게임에는 이상한 규칙이 더 있다. 두 발이 같은 지점에 있는 것이 허락되지 않는 것이다. (물론 게임 시작시에는 예외이다) 만약, 한 발이 1의 위치에 있고, 다른 한 발이 3의 위치에 있을 때, 3을 연속으로 눌러야 한다면, 3의 위치에 있는 발로 반복해야 눌러야 한다는 것이다.

오랫동안 DDR을 해 온 백승환은 발이 움직이는 위치에 따라서 드는 힘이 다르다는 것을 알게 되었다. 만약, 중앙에 있던 발이 다른 지점으로 움직일 때, 2의 힘을 사용하게 된다. 그리고 다른 지점에서 인접한 지점으로 움직일 때는 3의 힘을 사용하게 된다. (예를 들면 왼쪽에서 위나 아래로 이동할 때의 이야기이다.) 그리고 반대편으로 움직일때는 4의 힘을 사용하게 된다. (위쪽에서 아래쪽으로, 또는 오른쪽에서 왼쪽으로). 만약 같은 지점을 한번 더 누른다면, 그때는 1의 힘을 사용하게 된다.

만약 1 → 2 → 2 → 4를 눌러야 한다고 가정해 보자. 당신의 두 발은 처음에 (point 0, point 0)에 위치하여 있을 것이다. 그리고 (0, 0) → (0, 1) → (2, 1) → (2, 1) → (2, 4)로 이동하면, 당신은 8의 힘을 사용하게 된다. 다른 방법으로 발을 움직이려고 해도, 당신은 8의 힘보다 더 적게 힘을 사용해서 1 → 2 → 2 → 4를 누를 수는 없을 것이다.

 

---

 

시작 위치에서 (0, 0)를 시작으로 눌러야 하는 번호가 순차적으로 주어진다. 우리는 그 번호를 다양한 방법을 통해 누를 수 있는데 번호를 옮겨갈 때 드는 힘의 사용량은 다르다. 모든 번호를 누르는데 드는 최소힘을 구해야한다.

 

최소힘을 구하기 위해 모든 방법을 시도하는 완전탐색을 베이스로 + 같은 방법으로 진행할 여지가 있는 부분은 메모이제이션을 적용하여 동적계획법으로 해결할 수 있다.

 

메모이제이션을 적용하는 방법은 다양한 방법이 있겠지만,

나는 [현재 위치에서의 / 왼발과 / 오른발의 위치]로 설정하였다. 재귀 형태로 구현할 것이기 때문에 끝까지 시도해서 진행한 결과를 위에 형태 배열에 저장할 것이다. 그리고 같은 위치로 왼발과 오른발의 위치도 같은 상태로 다시 온다면 값만 반환받는 방법이다.

 

#include <iostream>
#include <vector>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define INF 987654321
#define endl '\n'

using namespace std;

vector<int> pos;
int cache[100000 + 1][5][5];

void input() {
	while (1) {
		int x; cin >> x;
		if (!x) break;
		pos.push_back(x);
	}
}

int dist(int cur, int next) {
	if (!cur) return 2;
	if (cur == next) return 1;
	if (cur == 1 && (next == 2 || next == 4)) return 3;
	if (cur == 2 && (next == 1 || next == 3)) return 3;
	if (cur == 3 && (next == 2 || next == 4)) return 3;
	if (cur == 4 && (next == 1 || next == 3)) return 3;
	return 4;
}

int path(int index, int left, int right) {
	if (index == pos.size()) return 0;
	int& ret = cache[index][left][right];
	if (ret != -1) return ret;

	ret = INF;
	return ret = min({ ret, path(index + 1, pos[index], right) + dist(left, pos[index])
			, path(index + 1, left, pos[index]) + dist(right, pos[index]) });
}

int solution() {
	memset(cache, -1, sizeof(cache));
	return path(0, 0, 0);
}

int main() {
	fastio;
	input();
	cout << solution() << endl;

	return 0;
}