취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2518번 문제인 회전 테이블이다.
문제는 아래 링크를 확인하자.

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

편의상 요리의 인덱스를 문제와 같은 1-based가 아닌 0-based를 기준으로 풀겠다.

먼저 "엄마"와 "현이"가 자신이 먹고싶은 음식이 본인 앞에 있을 때의 상황을 그 때 "아빠" 앞에 놓인 요리의 번호로 나타내자. 이렇게 인덱스의 기준을 통일시키면 앞으로의 구현에서 혼동이 적게 된다.

이제, dp[x][y][z][i] 을 ("아빠"가 x번 요리까지, "엄마"가 y번 요리까지, "현이"가 z번 요리까지 순서대로 먹은 상태 가운데 마지막으로 음식을 먹은 사람이 i=0이면 "아빠", i=1이면 "엄마", i=2이면 "현이"를 만족하는 식사방식 중 중 테이블 회전횟수의 최솟값) 으로 정의하자. 이 때 i=0이면 dp[x][y][z][i]는 dp[x-1][y][z][0], dp[x-1][y][z][1], dp[x-1][y][z][2] 세 값을 이용해 계산할 수 있음을 알 수 있다. 이와 비슷하게 i=1, i=2인 경우 또한 앞선 dp값을 이용해 계산해낼 수 있음을 관찰할 수 있다. (단, i에 대응되는 사람이 주어진 상태에서 마지막으로 식사를 할 수 없는 경우 테이블의 회전횟수를 무한대와 같이 취급해주자. 또한 아직 아무도 식사를 하지 않은 dp[0][0][0][0], dp[0][0][0][1], dp[0][0][0][2]의 경우 적절하게 초기값을 넣어주자.)

위와 같은 점화관계를 이용해 문제를 해결하자. 시간복잡도는 각자가 먹고싶은 요리개수의 최댓값을 P라 할 때 $O(P^3)$과 같다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N, X, Y, Z;
int arrX[101], arrY[101], arrZ[101];
int dp[101][101][101][3];
bool visited[101][101][101][3];

int dist(int x, int y) {
	int ret = abs(x - y);
	return min(ret, N - ret);
}

int func(int x, int y, int z, int i) {
	int& ret = dp[x][y][z][i];
	if (visited[x][y][z][i]) return ret;
	visited[x][y][z][i] = 1;

	ret = 1000000007;
	if (i == 0) {
		if (x) {
			ret = min(ret, func(x - 1, y, z, 0) + dist(arrX[x - 1], arrX[x]));
			ret = min(ret, func(x - 1, y, z, 1) + dist(arrY[y], arrX[x]));
			ret = min(ret, func(x - 1, y, z, 2) + dist(arrZ[z], arrX[x]));
		}
	}
	else if (i == 1) {
		if (y) {
			ret = min(ret, func(x, y - 1, z, 0) + dist(arrX[x], arrY[y]));
			ret = min(ret, func(x, y - 1, z, 1) + dist(arrY[y - 1], arrY[y]));
			ret = min(ret, func(x, y - 1, z, 2) + dist(arrZ[z], arrY[y]));
		}
	}
	else {
		if (z) {
			ret = min(ret, func(x, y, z - 1, 0) + dist(arrX[x], arrZ[z]));
			ret = min(ret, func(x, y, z - 1, 1) + dist(arrY[y], arrZ[z]));
			ret = min(ret, func(x, y, z - 1, 2) + dist(arrZ[z - 1], arrZ[z]));
		}
	}

	return ret;
}

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

	cin >> N;

	cin >> X;
	for (int x = 1; x <= X; x++) {
		cin >> arrX[x];
		arrX[x]--;
	}
	cin >> Y;
	for (int y = 1; y <= Y; y++) {
		cin >> arrY[y];
		arrY[y]--;
		arrY[y] -= N / 3;
		if (arrY[y] < 0) arrY[y] += N;
	}
	cin >> Z;
	for (int z = 1; z <= Z; z++) {
		cin >> arrZ[z];
		arrZ[z]--;
		arrZ[z] += N / 3;
		if (arrZ[z] >= N) arrZ[z] -= N;
	}

	dp[0][0][0][1] = dp[0][0][0][2] = N / 3;
	visited[0][0][0][0] = visited[0][0][0][1] = visited[0][0][0][2] = 1;

	cout << min(func(X, Y, Z, 0), min(func(X, Y, Z, 1), func(X, Y, Z, 2)));
}