[boj : 2666] 벽장문의 이동

www.acmicpc.net/problem/2666

2666번: 벽장문의 이동

문제 : n개의 벽이 주어지고 단2개만 빼고 전부 벽장문이 존재합니다. 이 벽장문을 한칸씩 양옆중 한방향으로 밀어 원하는 인덱스의 벽에 접근하면 됩니다. 이때 벽장문의 이동의 최소값을 구하는게 문제입니다.

 

해설: 먼저 어떻게 문제에 접근할까 부터 생각을 해보았습니다.

벽을 차례대로 사용할 번호를 배열에 담고 순차적으로 접근해야 함을 첫번째로 고려하였습니다.

그러면 사용하고자 하는 벽장과 가장 가까이에 벽장문이 존재하지 않는 벽장을 선택하여 옮겨주면 되는 것이 아닌가?라는 생각을 하였지만 이는 전체 과정을 수행하였을때 최적의 답이 된다는 보장이 되지 않습니다.(즉, 그리디 하게 선택하였을때 답을 도출하지 못한다는 뜻입니다) 그러면 다이나믹 프로그래밍을 사용하는 걸 생각할 수 있습니다.

 

벽장문이 열린 곳은 단 2곳입니다. 이 두가지 경우에 대해 전부 생각하며 최소값을 저장해 두고 저장된 값을 그대로 사용하면 되겠습니다.

 

점화식 : dp[cnt][x][y] = x번째와 y번째 벽장문이 존재하지 않고 cnt 번째 도달하였을때 최소값

 

#include<bits/stdc++.h>

using namespace std;

int n, a, b, t;
int dp[25][25][25], arr[20];

int f(int x, int y, int z);

int main()
{
	cin >> n >> a >> b >> t;
	for (int i = 1; i <= t; i++)
		cin >> arr[i];
	for(int p=1;p<=t;p++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				dp[p][i][j] = (int)1e9;

	cout << f(a, b, 1);	
	return 0;
}
int f(int x, int y, int z)
{
	if (z == t+1)return 0;
	int& ret = dp[z][x][y];
	if (ret != (int)1e9)return ret;

	ret = min(ret, min(f(arr[z], y, z + 1) + abs(x - arr[z]), f(x, arr[z], z + 1) + abs(y - arr[z])));
	return ret;
}