Boj 2618) 경찰차

DP

백준 2618

방법 0

Gridy 방법으로 푸는 방법은 통하지 않는다.

왜냐하면 경찰차 둘로부터 거리가 같은 경우 어느걸 먼저 선택할지 정할 수 없어서 모두 고려해야하기 때문이다.

방법 1

설명

dp[y][x] 를 경찰차 A 가 마지막으로 출동한 사건이 x, 경찰차 B 가 마지막으로 출동한 사건이 y 라고 해석하자.

이때 동시에 출동할 순 없으므로 x != y 가 만족되어야 한다.

이때 두가지 성질이 나타난다.

• abs(x-y) > 1 의 경우 가장 최근에 출동한 차가 또 출동한 경우가 됨.
• abs(x-y) == 1 의 경우 가장 최근에 출동한 차는 출동하지 않음
  • 그래서 최근에 출동하지 않은 차가 언제 출동했는지 모든 경우를 다 고려함

위 성질을 통해서 dp 를 채우고 값 trace 의 경우 역추적을 하면 된다.

개고생 기록

tmp1 = INT_MAX;
for (int i = 0; i < x; i++)
{
	tmp2 = dp[i][x] + Dist(GetLocB(i), GetLocB(y));
	if (tmp2 < tmp1)
	{
		tmp1 = tmp2;
		y = i;
	}
}

Trace 를 할 때 위처럼 구했는데 답이 안나온다고 몇시간을 헤멨다.

알고보니 y 를 tmp2 계산할 때 사용하는데, 최솟값 업데이트 때 y 를 수정해서 그런거였다.

시간 복잡도

O(n^2)

공간 복잡도

O(n^2)

코드

#define INT_MAX 200000000
struct LOC {
	LOC() : x(0), y(0) {}
	LOC(int x, int y) : x(x), y(y) {}
	int x, y;
};
vector<LOC> locs;
int Dist(const LOC& in1, const LOC& in2) { return abs(in1.x - in2.x) + abs(in1.y - in2.y); }
LOC& GetLocA(int idx) {
	if (idx == 0) return locs[0];
	return locs[idx + 1];
}
LOC& GetLocB(int idx) {
	if (idx == 0) return locs[1];
	return locs[idx + 1];
}

int dp[1001][1001];

int main()
{
	int n, t, tmp1, tmp2;
	cin >> n >> t;
	locs.emplace_back(1, 1);
	locs.emplace_back(n, n);
	for (int i = 0; i < t; i++)
	{
		cin >> tmp1 >> tmp2;
		locs.emplace_back(tmp1, tmp2);
	}

	// DP Calc
	dp[0][1] = Dist(locs[0], locs[2]);
	dp[1][0] = Dist(locs[1], locs[2]);
	for (int i = 2; i <= t; i++)
	{
		// Make dp[0~i-2][i]
		for (int j = 0; j < i - 1; j++)
			dp[j][i] = dp[j][i - 1] + Dist(GetLocA(i - 1), GetLocA(i));
	
		// Make dp[i-1][i]
		tmp1 = INT_MAX;
		for (int j = 0; j < i - 1; j++)
		{
			tmp2 = dp[i - 1][j] + Dist(GetLocA(j), GetLocA(i));
			if (tmp2 < tmp1)
				dp[i - 1][i] = tmp1 = tmp2;
		}
	
		// Make dp[i][0~i-2]
		for (int j = 0; j < i - 1; j++)
			dp[i][j] = dp[i - 1][j] + Dist(GetLocB(i - 1), GetLocB(i));
	
		// Make dp[i][i-1]
		tmp1 = INT_MAX;
		for (int j = 0; j < i - 1; j++)
		{
			tmp2 = dp[j][i - 1] + Dist(GetLocB(j), GetLocB(i));
			if (tmp2 < tmp1)
				dp[i][i - 1] = tmp1 = tmp2;
		}
	}
	
	// Cost
	int x, y;
	int r = INT_MAX;
	for (int i = 0; i < t; i++)
	{
		r = min(r, dp[i][t]);
		if (r == dp[i][t]) {
			x = t; y = i;
		}
		r = min(r, dp[t][i]);
		if (r == dp[t][i]) {
			x = i; y = t;
		}
	}
	cout << r << '\n';
	
	// Trace
	vector<char> ans;
	while (x + y > 0)
	{
		if (x > y)
		{
			ans.push_back('1');
			if (x > y + 1 || y == 0)
				x--;
			else {
				for (int i = 0; i < y; i++)
				{
					if ( dp[y][x] == dp[y][i] + Dist(GetLocA(i), GetLocA(x)))
						x = i;
				}
			}
		}
		else
		{
			ans.push_back('2');
			if (y > x + 1 || x == 0)
				y--;
			else {
				for (int i = 0; i < x; i++)
				{
					if (dp[y][x] == dp[i][x] + Dist(GetLocB(i), GetLocB(y)))
						y = i;
				}
			}
		}
	}
	
	for (auto i = ans.rbegin(); i != ans.rend(); i++)
		cout << *i << '\n';
}

방법 2

설명

방법 1 에서 점화식을 잘 보자.

		// Make dp[0~i-2][i]
		for (int j = 0; j < i - 1; j++)
			dp[j][i] = dp[j][i - 1] + Dist(GetLocA(i - 1), GetLocA(i));
	
		// Make dp[i-1][i]
		tmp1 = INT_MAX;
		for (int j = 0; j < i - 1; j++)
		{
			tmp2 = dp[i - 1][j] + Dist(GetLocA(j), GetLocA(i));
			if (tmp2 < tmp1)
				dp[i - 1][i] = tmp1 = tmp2;
		}

i-1 이 중복되는 것이 보인다.

우리에게 필요한 것은 가장 최근에 경찰차를 움직이고 남은 정보이기 때문에 그런 것이다.

그렇기 때문에 우리는 공간복잡도를 선형으로 줄일 수 있다.

즉 방법1 에서 배열의 크기를 줄이고 경로 추적용으로 배열을 추가로 두기만 하면 된다.

그러면 dp[x][cop] 은 x보다 큰 값인 가장 최근 사건에 cop 이 움직였고 cop 말고 다른 경찰차가 마지막으로 움직인게 x 라는 말이 된다.

시간 복잡도

O(n^2),

공간 복잡도

O(n)

코드

#define INT_MAX 200000000
struct LOC {
	LOC() : x(0), y(0) {}
	LOC(int x, int y) : x(x), y(y) {}
	int x, y;
};
LOC locs[1001];
LOC& GetLoc(int idx, int isB) { if (idx == 0) return locs[isB]; return locs[idx + 1]; }
int Dist(const LOC& in1, const LOC& in2) { return abs(in1.x - in2.x) + abs(in1.y - in2.y); }


int dp[1001][2]; // dp[x][cop] => x is last moved idx of other cop 
int his[1001][2];
char ans[1001];

int main()
{
	int n, t, tmp1, tmp2;
	cin >> n >> t;
	locs[0] = { 1, 1 };
	locs[1] = { n, n };
	for (int i = 0; i < t; i++)
	{
		cin >> tmp1 >> tmp2;
		locs[i + 2] = { tmp1, tmp2 };
	}

	// Initial DP
	for (int cop = 0; cop < 2; cop++)
		dp[0][cop] = Dist(GetLoc(0, cop), GetLoc(1, cop));
	
	for (int i = 2; i <= t; i++)
	{
		// Update If other is moved before and this is to move
		for (int cop = 0; cop < 2; cop++)
		{
			dp[i - 1][cop] = INT_MAX;
			for (int j = 0; j < i - 1; j++)
			{
				tmp1 = dp[j][!cop] + Dist(GetLoc(j, cop), GetLoc(i, cop));
				if (tmp1 < dp[i - 1][cop])
				{
					dp[i - 1][cop] = tmp1;
					his[i - 1][cop] = j;
				}
			}
		}
		// Update If other is not moved before and this is to move
		for (int cop = 0; cop < 2; cop++)
			for (int j = 0; j < i - 1; j++)
				dp[j][cop] += Dist(GetLoc(i - 1, cop), GetLoc(i, cop));
	}
	
	int r = INT_MAX; int ans_idx, ans_cop;
	for (int i = 0; i < t; i++)
		for (int cop = 0; cop < 2; cop++)
		{
			if (r > dp[i][cop])
			{
				r = min(r, dp[i][cop]);
				ans_idx = i;
				ans_cop = cop;
			}
		}
	
	cout << r << '\n';
	
	for (int i = t; i > 0; i--)
	{
		if (i == ans_idx) {
			ans_idx = his[ans_idx][ans_cop];
			ans_cop = !ans_cop;
		}
		ans[i - 1] = ans_cop ? '2' : '1';
	}
	
	for (auto i = 0; i < t; i++)
		cout << ans[i] << '\n';

}