[C++] 백준 2666번: 벽장문의 이동

문제 링크

2666번: 벽장문의 이동

문제 요약

벽장이 있고, 2개의 벽장문이 존재한다. 벽장문은 인접한 벽장 앞에 벽장문이 없다면 밀어서 1칸 이동시킬 수 있다. 벽장들의 이용 순서가 주어질 때, 벽장 문의 이동 횟수의 최솟값을 구해야 한다.

접근 방법

벽장의 갯수가 최대 20개입니다. 두 개의 벽장문 중에 하나를 골라서 사용한다고 했을 때, 최대 $2^{20}$번까지 확인을 해보면 됩니다. 단, 좌우 맨 끝의 벽장은 이용할 수 있는 벽장문이 하나뿐이기 때문에 이러한 경우는 별도로 처리해 주어야 합니다.

만약 현재 고르고자 하는 벽장이 두 벽장문의 사이에 있다면 다른 벽장문의 간섭 없이 두 벽장문 모두 선택이 가능합니다.

하지만 고르고자 하는 벽장이 왼쪽 벽장문보다 왼쪽에 있는 경우, 또는 오른쪽 벽장문보다 오른쪽에 있는 경우는 별도의 처리가 필요합니다. 이런 경우에는 더 먼 벽장문을 고르기 위해서는 가까운 벽장문을 더 밀어내야 합니다. 그래서 이런 경우를 분기로 처리해주었습니다.

코드

#include <bits/stdc++.h>

using namespace std;

int n, m, res = INT_MAX;

void func(vector<int> v, int idx, int move, int o1, int o2)
{
	if (idx == v.size())
	{
		res = min(res, move);
		return;
	}

	if (v[idx] == 1)
		func(v, idx + 1, move + o1 - v[idx], v[idx], o2);
	else if (v[idx] == n)
		func(v, idx + 1, move + v[idx] - o2, o1, v[idx]);
	else
	{
		if (v[idx] > o1 && v[idx] < o2)
		{
			func(v, idx + 1, move + v[idx] - o1, v[idx], o2);
			func(v, idx + 1, move + o2 - v[idx], o1, v[idx]);
		}
		else if (v[idx] <= o1)
		{
			func(v, idx + 1, move + o1 - v[idx], v[idx], o2);
			func(v, idx + 1, move + o1 - (v[idx] - 1) + o2 - v[idx], v[idx] - 1, v[idx]);
		}
		else
		{
			func(v, idx + 1, move + v[idx] - o2, o1, v[idx]);
			func(v, idx + 1, move + (v[idx] + 1) - o2 + v[idx] - o1, v[idx], v[idx] + 1);
		}
	}
}

int main(void)
{
	int open1, open2;
	cin >> n >> open1 >> open2 >> m;

	if (open1 > open2)
		swap(open1, open2);

	vector<int> v(m);
	for (int i = 0; i < m; i++)
		cin >> v[i];

	func(v, 0, 0, open1, open2);
	cout << res;
	return 0;
}