[백준(BOJ)] 경찰차(2618번)_C++

어려움.

처음엔 dp[2][1001] 배열로 1이 움직일 때와 2가 움직일 때를 dp로 구현하려 했다.

문제점은 사건을 진행할 때마다 변경되는 각 경찰차의 위치와 사건진행 순서를 관리하기 어렵다는 것이었다.

그러다 기가막힌 방법을 하나 어디서 주워들었다.

 

dp[i][j] 가 1이 i번 사건까지 2는 j번 사건까지 해결했을 때의 최소 거리임을 의미하는 dp[1001][1001] 배열을 만드는 것이다.

즉, 각 경찰차가 마지막으로 진행한 사건 번호를 저장하는 것이었다. 그러면 굳이 좌표를 저장할 필요가 없었다.

dfs를 진행하면서 최소 거리를 찾으면서 dp 배열을 채운다.

 

각 경찰차의 사건 진행 순서도 비슷한 로직으로 구현할 수 있다.

이미 구해진 dp 배열을 이용해서 순서를 구할 수 있다.

 

코드를 조금씩 분석해보면서 이해해보기를 바란다.

 

 

---

정답

#include <iostream>
#include <cstring>

using namespace std;

int n, w;
pair<int, int> event[1001];
int dp[1001][1001];

int dfs(int p1, int p2){

	//last event
	if (p1 == w || p2 == w)
		return 0;

	//already calculate
	if (dp[p1][p2] != -1)
		return dp[p1][p2];

	int next = max(p1, p2) + 1;

	int dist1, dist2;

	if (p1 == 0)
		dist1 = abs(1 - event[next].first) + abs(1 - event[next].second);
	else
		dist1 = abs(event[p1].first - event[next].first) + abs(event[p1].second - event[next].second);

	if (p2 == 0)
		dist2 = (n - event[next].first) + (n - event[next].second);
	else
		dist2 = abs(event[p2].first - event[next].first) + abs(event[p2].second - event[next].second);

	int res1 = dfs(next, p2) + dist1;
	int res2 = dfs(p1, next) + dist2;

	dp[p1][p2] = min(res1, res2);

	return dp[p1][p2];
}

void print_order(int p1, int p2){

	if (p1 == w || p2 == w)
		return ;

	int next = max(p1, p2) + 1;

	int dist1, dist2;

	if (p1 == 0)
		dist1 = abs(1 - event[next].first) + abs(1 - event[next].second);
	else
		dist1 = abs(event[p1].first - event[next].first) + abs(event[p1].second - event[next].second);

	if (p2 == 0)
		dist2 = (n - event[next].first) + (n - event[next].second);
	else
		dist2 = abs(event[p2].first - event[next].first) + abs(event[p2].second - event[next].second);

	int res1 = dp[next][p2] + dist1;
	int res2 = dp[p1][next] + dist2;

	if (res1 < res2){
		cout << 1 << "\n";
		print_order(next, p2);
	}
	else{
		cout << 2 << "\n";
		print_order(p1, next);
	}
}

int main(){
	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	//input
	cin >> n >> w;
	for(int i = 1; i <= w; i++)
		cin >> event[i].first >> event[i].second;

	memset(dp, -1, sizeof(dp));

	//calculate min distance and output
	cout << dfs(0, 0) << "\n";
	print_order(0, 0);
}