백준 2618 경찰차

DP  문제입니다. 

 

이전에 풀었던 환상의 듀엣 이란 문제와 유사한데 경찰차가 이동하는 지점이 반드시 정해져 있습니다.

 

즉 두 경찰차는 반드시 시작지점이 아니면 사건이 발생한 어느지점에 위치하고 있기 때문에 DP 배열을 아래와 같이 정의 할 수 있습니다.

DP[i][j] = 1번 경찰차가 마지막으로 해결한사건(i), 2번 경찰차가 마지막으로 해결한사건(j) 일때의 최소 이동거리

 

저렇게 정의한다면 우리는 max(i,j) + 1이 다음사건임을 알 수 있습니다. 

 

이 문제는 여기서 끝이 아니라 이 최소비용을 얻었을때 각 사건을 어떤 경찰차가 해결하였는지 까지 출력을 하여야 합니다. 처음에 이 경로를 어떻게 구해야 할지 생각이 안났는데 먼저 최소 비용을 구한 후 다시 0,0 부터 시작하며 자신이 선택한 경로를 따라가면 쉽게 찾을 수 있습니다. 각 함수에서 1번이 해결한 경우 / 2번이 해결한 경우로 나뉘는데 이 두값중 우리는 작은 값을 택하면서 내려왔으므로 작은 값을 택하는 경우를 찾아서 다시 올라가면 됩니다!

 

말보다는 아무래도 코드로 보시면 이해가 쉬울 것 같습니다.

 

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <stack>

#define INF 987654321
using namespace std;

vector<pair<int, int> > pr;

int dp[1010][1010]; //i: 1번 경찰차가 마지막으로 방문한 곳 j: 2번 경찰차가 마지막 방문 했을때 최소값

int N;
int w;
int ans = INF;
stack<int> s;

int sol(int first, int second) {
	
	if (first == w || second == w) {
		
		return 0;
	}

	int &ret = dp[first][second];
	if (ret != -1) return ret;

	int next = max(first, second) + 1; //다음 사건
	int dist1, dist2;
	
	if(first == 0) dist1 = abs(pr[next - 1].first - 1) + abs(pr[next - 1].second -1);
	else dist1 = abs(pr[next - 1].first - pr[first - 1].first) + abs(pr[next - 1].second - pr[first - 1].second);

	if(second == 0) dist2 = abs(pr[next - 1].first - N) + abs(pr[next - 1].second - N);
	else dist2 = abs(pr[next - 1].first - pr[second - 1].first) + abs(pr[next - 1].second - pr[second - 1].second);


	int left = sol(next, second) + dist1;
	int right = sol(first, next) + dist2;

	ret = min(left, right);

	return ret;
}



void back(int first, int second) {
	
	if (first == w || second == w) {
		return;
	}

	int next = max(first, second) + 1; //다음 사건
	int dist1, dist2;

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

	if (second == 0) dist2 = abs(pr[next - 1].first - N) + abs(pr[next - 1].second - N);
	else dist2 = abs(pr[next - 1].first - pr[second - 1].first) + abs(pr[next - 1].second - pr[second - 1].second);


	if (dp[next][second] + dist1 > dp[first][next] + dist2) {
		cout << 2 << '\n';
		back(first, next);
	}
	else {
		cout << 1 << '\n';
		back(next, second);
	}
	return;
}


int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	memset(dp, -1, sizeof(dp));
	cin >> N; 
	cin >> w;

	for (int i = 0; i < w; i++) {
		int x, y; cin >> x >> y;
		pr.push_back({ x,y });
	}	

	cout << sol(0, 0) << '\n';
	back(0, 0);
	return 0;
}