[PS] 정올 4101번 Mountain View

Об этом предложении

문제 설명 각 산은 밑변이 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) 입니다.