[백준 2342] Dance Dance Revolution (C++)

이 문제는 기존의 발들의 위치를 기반으로 발을 다음 위치로 이동시킬때, 힘이 최소가 되도록 해야한다.

즉, 이전 값을 통해 새로운 값을 추론하는 과정이므로 DP로 접근이 가능하다.

그런데, 위치 정보는 왼발과 오른발의 위치로 2차원으로 나타내어져야한다.

그렇기 때문에 3차원 DP로 접근해야하고, d[i][j][k]는 i번째까지 왼발의 위치가 j, 오른발의 위치가 k인 경우 필요한 힘의 최소값이 저장되도록 해야한다.

점화식은 DP가 그렇듯 테이블을 그려보면 된다.

입력이 1, 2, 2, 4, 0라고 가정하고 테이블을 그려보자.

$i = 1$

j\k	0	1	2	3	4
0	0	2	0	0	0
1	2	0	0	0	0
2	0	0	0	0	0
3	0	0	0	0	0
4	0	0	0	0	0

$i = 2$

j\k	0	1	2	3	4
0	0	0	5	0	0
1	0	0	4	0	0
2	5	4	0	0	0
3	0	0	0	0	0
4	0	0	0	0	0

$i = 3$

j\k	0	1	2	3	4
0	0	0	6	0	0
1	0	0	5	0	0
2	6	5	7	0	0
3	0	0	0	0	0
4	0	0	0	0	0

$i = 4$

j\k	0	1	2	3	4
0	0	0	0	0	10
1	0	0	0	0	9
2	0	0	0	0	8
3	0	0	0	0	0
4	10	9	8	0	0

먼저, $i$번째에 밟아야 할 위치를 $x$라 하고, $i-1$번째에서의 발의 위치를 $(j, k)$라 하자.

이때, 오른발과 왼발을 각각 움직여 $x$를 밟을 수 있다.
단, 기존에 발이 있었던 위치에서 새로운 위치의 값을 이끌어내야 하므로, d[i-1][j][k]값이 0이 아님이 전제되어야 한다.

해당 위치에서 $x$를 밟는 경우는 $(x, k), (j, x)$가 된다.
각각 왼발과 오른발로 $x$를 밟은 것이다.

따라서, d[i-1][j][k]가 0이 아닌지 먼저 판별하고 d[i][j][x]와 d[i][x][k]값을 유도해 나갈 수 있다.

발을 이동할 때 드는 힘은 같은 위치면 1, 중앙에서 다른 위치로는 2, 인접한 위치로는 3, 정반대 위치로는 4가 든다.

이 과정을 왼발과 오른발에 대해 반복해야하므로, 함수로 따로 빼놓는 게 좋을 것같다.

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

int x;
int d[100'001][5][5];

int force(int i, int j) {
	if (i == 0) return 2;
	if (i == j) return 1;
	if (abs(i - j) == 2) return 4;
	return 3;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int i = 1;
	cin >> x;
	if (!x) {
		cout << 0;
		return 0;
	}

	d[i][0][x] = 2, d[i][x][0] = 2;
	while (1) {
		cin >> x;
		if (!x) break;
		i++;
		for (int j = 0; j < 5; j++) {
			for (int k = 0; k < 5; k++) {
				if (!d[i - 1][j][k]) continue;

				int f = force(k, x);
				if (d[i][j][x]) d[i][j][x] = min(d[i - 1][j][k] + f, d[i][j][x]);
				else d[i][j][x] = d[i - 1][j][k] + f;

				f = force(j, x);
				if (d[i][x][k]) d[i][x][k] = min(d[i - 1][j][k] + f, d[i][x][k]);
				else d[i][x][k] = d[i - 1][j][k] + f;
			}
		}
	}

	int ans = 0x7f7f7f7f;
	for (int j = 0; j < 5; j++) {
		for (int k = 0; k < 5; k++) {
			if (!d[i][j][k]) continue;
			ans = min(ans, d[i][j][k]);
		}
	}

	cout << ans;
}