[BOJ] 2618 경찰차

(2021년 1월 13일에 작성한 글입니다.)

 

2618번: 경찰차

신기하도다

정말 신기하다

​

처음에는 dp[1][i]는 i번째 사건을 1번 차가 처리,

dp[2][i]는 i번째 사건을 2번 차가 처리...

이렇게 해서 점화식을 세우면 될 줄 알았는데

말이 안 되는 풀이였다..

그래서 결국 여러가지 풀이를 찾아봤고

재귀를 사용한 dp였다...

​

그리고 2차원 dp 배열은

1번 차가 i번째 사건, 2번 차가 j번째 사건을 처리했을 때 최소 이동거리를 저장하고 있다.

진짜 신기하다.

​

모든 사람이 재귀로 풀었길래

이중 for문으로 확인하는 건 왜 안되는지 너무 궁금했는데

​

저렇게 하면... 점화식을 세우기가 힘들다.

i == j라면 i번째 사건을 1, 2번 차가 모두 해결한다는 뜻이니까

이런 건 말이 안 되서 i == j일때를 따로 처리해줘야 한다.

그래서 처음엔 이런 경우에 dp[i][i] = min(dp[i-1][i], dp[i][i-1])를 하고

나머지 경우에는 dp[i][j] = min(dp[i-1][j]+dist, dp[i][j-1]+dist)

이런식으로 하면 될 것 같았는데

​

지금 다시 보니까 말이 안 된다...

max(i, j)까지 해결한 상태라는 그 포인트도 못 잡았던 거 같다...

​​

지금 글을 쓰면서 또 정리됐는데

dp[i][j]에는 1번 차가 i번째, 2번 차가 j번째 사건을 해결했을 때

W + 2번 사건까지 해결하기 위해서 더 가야하는 거리가 저장되어 있구나.

그래서 solve(1, 2) 값을 출력하면 되는거고... ( == dp[1][2] )

그랬구나..

​

생각을 더 정리하자.

​

그리고 또

1번, 2번 차의 초기 위치를 어떻게 처리하면 되는지는

solve 함수 내에서 if문으로 각각의 차들이 처음 상태인지를 확인하는 방법과

차들의 처음 위치를 좌표와 함께 저장하는 방법도 있다.

나는 후자로 했는데

arr[1] = {1, 1}, arr[2] = {N, N}이고

arr[3] ~ arr[W + 2]까지 input 값을 저장했다.

​​

신기하다...

vector<pair<int, int>> arr;
vector<vector<int>> dp;
int W;

int getDist(pair<int, int> a, pair<int, int> b);
int solve(int, int);
void print(int, int);

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

	cin >> N >> W;
	arr.resize(W + 5);
	arr[1] = { 1, 1 };
	arr[2] = { N, N };
	for (i = 3; i <= W + 2; i++) {
		cin >> arr[i].first >> arr[i].second;
	}

	dp.resize(W + 5, vector<int> (W + 5, -1));
	cout << solve(1, 2) << ENDL;
	print(1, 2);	

	return 0;
}

int getDist(pair<int, int> a, pair<int, int> b) {
	return abs(a.first - b.first) + abs(a.second - b.second);
}

int solve(int car1, int car2)
{
	int cur = max(car1, car2);
	if (cur == W + 2) {
		return 0;
	}

	if (dp[car1][car2] != -1) {
		return dp[car1][car2];
	}
	
	dp[car1][car2] = 0;
	int case1 = solve(cur + 1, car2) + getDist(arr[car1], arr[cur + 1]);
	int case2 = solve(car1, cur + 1) + getDist(arr[car2], arr[cur + 1]);

	return dp[car1][car2] = min(case1, case2);
}

void print(int car1, int car2)
{
	int cur = max(car1, car2);
	if (cur == W + 2) {
		return;
	}

	int case1 = solve(cur + 1, car2) + getDist(arr[car1], arr[cur + 1]);
	int case2 = solve(car1, cur + 1) + getDist(arr[car2], arr[cur + 1]);

	if (dp[car1][car2] == case1) {
		cout << 1 << ENDL;
		return print(cur + 1, car2);
	}
	else {
		cout << 2 << ENDL;
		return print(car1, cur + 1);
	}
}