[백준 2342] Dance Dance Revolution

문제 링크 => 2342번: Dance Dance Revolution (acmicpc.net)

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를 누를 수는 없을 것이다.

 

---

 

다이나믹 프로그래밍 문제이다.

위 조건을 간단하게 정리하자면 다음과 같다.

이때 (left, right, i) 를 i번째에 왼쪽 발은 left, 오른쪽 발은 right에 위치한다고 하자.

 

1.  (a, b, i - 1) => (c, d, i) 이 허용되지 않는다. (a ≠ c, b ≠ d)

즉, 두 발이 동시에 움직이는 것을 허용하지 않는다.

 

2. (a, a, i) 의 경우 a = 0 을 제외한 나머지 1 ~ 4 에 대해서 허용되지 않는다.

즉, 0번 발판을 제외한 나머지 발판 위에 두 발이 있으면 안된다.

 

3. 점수 획득은 다음과 같은 경우로 분류할 수 있다.

(1) 발판 유지 : 1점 획득 

(2) 0 번 발판에서 1~4 번 발판으로 이동 : 2점 획득

(3) 1, 3번 발판에서 2, 4번 발판으로 이동 or 2, 4번 발판에서 1, 3번 발판으로 이동 : 3점 획득 

(4) 1번 발판에서 3번 발판으로 이동 or 2번 발판에서 4번 발판으로 이동 or 3번 발판에서 1번 발판으로 이동 or 4번 발판에서 2번 발판으로 이동 : 4점 획득

 

위 경우를 고려하여 획득할 수 있는 점수에 대한 함수는 다음과 같이 정의할 수 있다.

 

bool point1(int before, int cur) {
	return before == cur && cur != 0;
}

bool point2(int before, int cur) {
	return before == 0 && cur;
}

bool point3(int before, int cur) {
	if (before % 2) return cur % 2 == 0;
	return cur % 2 != 0;
}

void setPoint(int before, int cur, int& point) {
	if (point1(before, cur)) point = 1;
	else if (point2(before, cur)) point = 2;
	else if (point3(before, cur)) point = 3;
	else point = 4;
}

 

dp[left][right][i] = 왼쪽 발이 left 발판, 오른쪽 발이 right 발판일 때 i 번째에 획득할 수 있는 최소 포인트

position[i] = i번째에 눌러야 할 발판 번호

이때 dp 식을 정의할 때 다음과 같은 점화식을 세울 수 있다.

 

\(dp[left][position[i]][i] = min({ dp[left][position[i]][i], dp[left][right][i - 1] + point_{right} }) \)

\(dp[position[i]][right][i] = min({ dp[position[i]][right][i], dp[left][right][i - 1] + point_{left} }) \)

 

이때 위치할 수 없는 발판에 대해서는 INF 값을 할당하여 해당 경우에 대해서는 위와 같은 식을 적용하지 않고 continue 할 수 있도록 하는 것이 핵심이다.

 

 

Solution Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>

#define INF 1000000000
#define endl '\n'

using namespace std;

int position[100001];
int dp[5][5][100001];

bool point1(int before, int cur) {
	return before == cur && cur != 0;
}

bool point2(int before, int cur) {
	return before == 0 && cur;
}

bool point3(int before, int cur) {
	if (before % 2) return cur % 2 == 0;
	return cur % 2 != 0;
}

void setPoint(int before, int cur, int& point) {
	if (point1(before, cur)) point = 1;
	else if (point2(before, cur)) point = 2;
	else if (point3(before, cur)) point = 3;
	else point = 4;
}

void solution(int n) {
	int i, left, right, point_right, point_left;
	
	for (left = 0; left <= 4; left++) {
		for (right = 0; right <= 4; right++) {
			if (left == 0 && right == 0) continue;
			dp[left][right][0] = INF;
		}
	}

	for (i = 1; i <= n; i++) {
		for (left = 0; left <= 4; left++) 
			for (right = 0; right <= 4; right++) 
				dp[left][right][i] = INF;
		for (left = 0; left <= 4; left++) {
			for (right = 0; right <= 4; right++) {
				if (dp[left][right][i - 1] == INF) continue;
				setPoint(left, position[i], point_left);
				setPoint(right, position[i], point_right);
				dp[left][position[i]][i] = min({ dp[left][position[i]][i],
					dp[left][right][i - 1] + point_right});
				dp[position[i]][right][i] = min({ dp[position[i]][right][i],
					dp[left][right][i - 1] + point_left });
			}
		}
	}

	int result = INF;
	for (left = 0; left <= 4; left++) {
		for (right = 0; right <= 4; right++) {
			if (left == right) continue;
			result = min(result, dp[left][right][n]);
		}
	}

	cout << result;
}

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

	int x, n;
	n = 0;
	while (1) {
		cin >> x;
		if (x == 0) break;
		position[++n] = x;
	}
	solution(n);

	return 0;
}