문제 설명
각 산은 밑변이 x축에 놓인 삼각형입니다.
양쪽 빗변은 밑변과 각각 45도를 이루므로, 봉우리 좌표 (x, y)가 주어지면 산의 모양이 결정됩니다.
베시는 어떤 산의 봉우리가 다른 산의 내부나 경계에 있으면 그 산을 구별할 수 없습니다.
주어진 산들 중에서 다른 산에 가려지지 않는 산의 개수를 구하면 됩니다.
예를 들어 봉우리 좌표가 다음과 같다면,
(4, 6)
(7, 2)
(2, 5)(7, 2)의 봉우리는 (4, 6)인 산에 가려집니다.
나머지 두 산은 구별할 수 있으므로 정답은 2입니다.
풀이 아이디어
1. 산을 밑변 구간으로 바꾸기
봉우리가 (x, y)인 산을 생각해보겠습니다.
빗변의 기울기는 각각 1, -1이므로, 봉우리에서 x축까지 내려가는 동안 가로로도 y만큼 이동합니다.
따라서 밑변의 양 끝점은 다음과 같습니다.
왼쪽 끝점: x - y
오른쪽 끝점: x + y산 하나를 다음 구간으로 표현할 수 있습니다.
[x-y, x+y]모든 산의 빗변 기울기가 같으므로, 봉우리가 다른 산에 가려지는 조건을 밑변 구간이 다른 구간에 포함되는 조건으로 바꿀 수 있습니다.
다른 산의 시작점 <= 현재 산의 시작점
현재 산의 끝점 <= 다른 산의 끝점즉, 다른 구간에 포함되지 않는 구간의 개수를 구하면 됩니다.
2. 정렬 후 최대 끝점 확인하기
구간을 시작점 기준 오름차순으로 정렬합니다.
그러면 앞에서 확인한 구간들은 모두 현재 구간의 시작점 이하에서 시작합니다.
이 상태에서는 앞선 구간들의 최대 끝점만 기억하면 됩니다.
현재 끝점 <= 이전 최대 끝점
→ 앞선 구간에 포함됨
현재 끝점 > 이전 최대 끝점
→ 앞선 구간에 포함되지 않음시작점이 같다면 끝점이 큰 구간을 먼저 확인합니다.
그래야 같은 위치에서 시작하는 작은 구간을 가려지는 산으로 처리할 수 있습니다.
코드
#include <bits/stdc++.h>
using namespace std;
bool cmp(pair<int, int> a, pair<int, int> b) {
if (a.first == b.first) return a.second > b.second;
return a.first < b.first;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N;
cin >> N;
vector<pair<int, int>> mnt;
for (int i=0; i<N; i++) {
int x,y;
cin >> x >> y;
mnt.push_back({x-y, x+y});
}
sort(mnt.begin(), mnt.end(), cmp);
int max_ed = INT_MIN;
int ret=0;
for (auto[st, ed] : mnt) {
if (ed > max_ed) {
ret++;
max_ed = ed;
}
}
cout << ret;
return 0;
}풀이 흐름
- 산의 개수
N을 입력받습니다. - 각 봉우리
(x, y)를 밑변 구간[x-y, x+y]로 바꾸어 저장합니다. - 시작점 오름차순, 시작점이 같다면 끝점 내림차순으로 정렬합니다.
- 이전 구간들의 최대 끝점
max_ed를 초기화합니다. - 정렬된 구간을 앞에서부터 확인합니다.
- 현재 끝점이
max_ed보다 크면 보이는 산으로 세고,max_ed를 갱신합니다. - 보이는 산의 개수
ret를 출력합니다.
구현 포인트
1. mnt에 저장하는 값
vector<pair<int, int>> mnt;mnt에는 봉우리 좌표가 아닌 산의 밑변 구간을 저장합니다.
first = 밑변의 왼쪽 끝점
second = 밑변의 오른쪽 끝점입력 단계에서 바로 좌표를 변환합니다.
int x,y;
cin >> x >> y;
mnt.push_back({x-y, x+y});예제의 산들을 구간으로 바꾸면 다음과 같습니다.
(4, 6) → [-2, 10]
(7, 2) → [5, 9]
(2, 5) → [-3, 7]이렇게 바꾸면 삼각형의 겹침을 직접 계산하지 않고, 두 끝점으로 포함 관계를 확인할 수 있습니다.
2. 봉우리의 포함과 구간의 포함이 같은 이유
다른 산의 봉우리를 (X, Y)라고 하겠습니다.
현재 봉우리 (x, y)가 이 산의 내부나 경계에 있으려면 다음 조건을 만족해야 합니다.
y + |x-X| <= Y다른 산은 봉우리에서 가로로 1만큼 멀어질 때마다 높이가 1씩 낮아집니다.
따라서 현재 위치에서 다른 산의 높이는 Y - |x-X|이며, 현재 봉우리의 높이 y가 이 값 이하여야 합니다.
이 조건은 다음 두 조건으로 나눌 수 있습니다.
y + x - X <= Y
y + X - x <= Y정리하면 다음과 같습니다.
x + y <= X + Y
X - Y <= x - y이는 밑변 구간으로 보면 다음 조건입니다.
다른 산의 왼쪽 끝점 <= 현재 산의 왼쪽 끝점
현재 산의 오른쪽 끝점 <= 다른 산의 오른쪽 끝점따라서 구간이 포함되면 해당 산의 봉우리도 가려집니다.
3. 시작점이 같으면 끝점 내림차순으로 정렬하기
bool cmp(pair<int, int> a, pair<int, int> b) {
if (a.first == b.first) return a.second > b.second;
return a.first < b.first;
}기본 정렬 기준은 시작점 오름차순입니다.
시작점이 같다면 끝점이 큰 구간을 먼저 배치합니다.
예를 들어 다음 두 구간이 있다고 하겠습니다.
[1, 5]
[1, 8][1, 5]는 [1, 8]에 포함되므로 가려지는 산입니다.
작은 구간을 먼저 확인하면 아직 큰 구간을 보지 못했기 때문에 작은 구간도 정답에 포함할 수 있습니다.
따라서 다음 순서로 정렬합니다.
[1, 8]
[1, 5]큰 구간을 먼저 확인하여 최대 끝점을 8로 만들면, 작은 구간은 자연스럽게 제외됩니다.
4. max_ed의 의미
int max_ed = INT_MIN;max_ed는 현재 구간을 확인하기 전에 처리한 모든 구간의 끝점 중 최댓값입니다.
처음에는 확인한 구간이 없으므로 INT_MIN으로 초기화합니다. 이를 통해 첫 번째 구간은 정답에 포함됩니다.
정렬 이후 앞선 구간들은 모두 현재 구간보다 왼쪽 또는 같은 위치에서 시작합니다.
따라서 앞선 구간 중 끝점이 현재 끝점 이상인 구간이 있다면, 그 구간은 현재 구간을 포함합니다.
이 조건을 확인하기 위해 앞선 구간들을 다시 순회할 필요는 없습니다. 가장 큰 끝점인 max_ed만 비교하면 됩니다.
5. 끝점이 더 클 때만 정답에 포함하기
int ret=0;
for (auto[st, ed] : mnt) {
if (ed > max_ed) {
ret++;
max_ed = ed;
}
}st는 현재 구간의 시작점이고, ed는 끝점입니다.
시작점 관계는 정렬로 보장되어 있으므로 반복문에서는 끝점만 비교합니다.
ed <= max_ed
→ 앞선 구간에 포함됨
→ 정답에 포함하지 않음현재 끝점이 더 크다면 앞선 어느 구간에도 포함되지 않습니다.
ed > max_ed
→ 보이는 산
→ ret 증가
→ max_ed 갱신끝점이 같은 경우에도 현재 구간은 앞선 구간에 포함됩니다.
문제에서는 경계에 있는 봉우리도 보이지 않으므로, 조건은 >=가 아닌 >입니다.
조건을 만족하지 않을 때는 현재 끝점이 기존 최댓값 이하이므로 max_ed를 그대로 유지합니다.
6. 한 번 센 산을 나중에 취소하지 않아도 되는 이유
현재 구간을 정답에 포함했다면 앞선 구간에는 가려지지 않는다는 것을 확인한 상태입니다.
뒤에 나오는 구간의 시작점은 현재 시작점보다 크거나 같습니다.
시작점이 더 크다면 현재 구간 전체를 포함할 수 없습니다.
시작점이 같더라도 끝점 내림차순으로 정렬했으므로, 뒤에 나오는 구간의 끝점은 현재 끝점 이하입니다. 봉우리 위치가 같은 두 산은 없으므로 완전히 같은 구간도 없습니다.
따라서 뒤의 구간이 현재 산을 가릴 수 없으며, 한 번 증가시킨 ret를 다시 줄일 필요가 없습니다.
7. 예시로 보는 동작
예제의 구간들을 정렬하면 다음과 같습니다.
[-3, 7]
[-2, 10]
[5, 9]첫 번째 구간을 확인합니다.
ed = 7
7 > INT_MIN
ret = 1
max_ed = 7두 번째 구간은 끝점이 기존 최댓값보다 큽니다.
ed = 10
10 > 7
ret = 2
max_ed = 10세 번째 구간은 끝점이 기존 최댓값 이하입니다.
ed = 9
9 <= 10
가려지는 산이므로 제외따라서 최종 정답은 2가 됩니다.
시간복잡도
각 산을 밑변 구간으로 변환하는 데 O(N)이 필요합니다.
구간을 정렬하는 데 O(N log N), 정렬된 구간을 한 번 순회하는 데 O(N)이 필요합니다.
따라서 전체 시간복잡도는 O(N log N)입니다.
mnt에 산마다 구간 하나를 저장하므로 공간복잡도는 O(N)입니다.
