ABC_230_D - Destroyer Takahashi

[zeikar]

Problem link

https://atcoder.jp/contests/abc230/tasks/abc230_d

Problem Summary

모든 벽을 부수기 위해 최소 몇 번 펀치를 해야 하는지 구하는 문제.

Solution

모든 벽을 부숴야 하므로 정렬 후 왼쪽부터 쭉 나가면 될 것 같다.
근데 이게 생각보다 안돼서... 대회 중에 결국 못 풀었다

에디토리얼을 참고해서 재작성.

일단 정렬은 맞는데 오른쪽 좌표를 기준으로 정렬해야 한다. 해당 벽을 제거할 때 최대한 오른쪽을 제거해야 다른 벽도 같이 제거할 수 있기 때문이다.
제거하는 벽은 왼쪽 좌표가 제거할 좌표 + d - 1 이내이면 가능하다.
이 좌표를 넘어가면 한번에 부술 수 없으므로 다시 오른쪽 좌표에서 펀치를 날려야 한다.

Source Code

#include <iostream>
#include <algorithm>
#include <utility>
#include <queue>
#include <vector>
using namespace std;

int main() {
	int n, d;
	cin >> n >> d;

	vector< pair<int, int> > walls;

	for (int i = 1; i <= n; i++)
	{
		int l, r;
		cin >> l >> r;

		walls.push_back(make_pair(r, l));
	}

	sort(walls.begin(), walls.end());

	int ans = 0, x = -1987654321;
	for (int i = 0; i < walls.size(); i++)
	{
		int l = walls[i].second;
		int r = walls[i].first;

		if (l > x + d - 1)
		{
			ans++;

			x = r;
		}
	}

	cout << ans << endl;
}