You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
모든 벽을 부숴야 하므로 정렬 후 왼쪽부터 쭉 나가면 될 것 같다.
근데 이게 생각보다 안돼서... 대회 중에 결국 못 풀었다
에디토리얼을 참고해서 재작성.
일단 정렬은 맞는데 오른쪽 좌표를 기준으로 정렬해야 한다. 해당 벽을 제거할 때 최대한 오른쪽을 제거해야 다른 벽도 같이 제거할 수 있기 때문이다.
제거하는 벽은 왼쪽 좌표가 제거할 좌표 + d - 1 이내이면 가능하다.
이 좌표를 넘어가면 한번에 부술 수 없으므로 다시 오른쪽 좌표에서 펀치를 날려야 한다.
Source Code
#include<iostream>
#include<algorithm>
#include<utility>
#include<queue>
#include<vector>usingnamespacestd;intmain() {
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;
}
The text was updated successfully, but these errors were encountered:
Problem link
https://atcoder.jp/contests/abc230/tasks/abc230_d
Problem Summary
모든 벽을 부수기 위해 최소 몇 번 펀치를 해야 하는지 구하는 문제.
Solution
모든 벽을 부숴야 하므로 정렬 후 왼쪽부터 쭉 나가면 될 것 같다.
근데 이게 생각보다 안돼서... 대회 중에 결국 못 풀었다
에디토리얼을 참고해서 재작성.
일단 정렬은 맞는데 오른쪽 좌표를 기준으로 정렬해야 한다. 해당 벽을 제거할 때 최대한 오른쪽을 제거해야 다른 벽도 같이 제거할 수 있기 때문이다.
제거하는 벽은 왼쪽 좌표가 제거할 좌표 + d - 1 이내이면 가능하다.
이 좌표를 넘어가면 한번에 부술 수 없으므로 다시 오른쪽 좌표에서 펀치를 날려야 한다.
Source Code
The text was updated successfully, but these errors were encountered: