💡 PS
[BOJ] 17026 Mountain View
date
Mar 7, 2022
slug
boj-17026
author
status
Public
tags
PS
summary
Mountain View 문제에 대한 풀이입니다.
type
Post
thumbnail
category
💡 PS
updatedAt
Aug 3, 2023 09:04 AM
언어
문제
풀이
재밌는 문제였다.
산봉우리의 각도가 90도여서 산이 x축과 만나는 양 끝 지점이 x-y와 x+y이다. 이를 수직선상에 표현하여 문제를 단순화 할 수 있다. 결국 이 문제는 시작점이 x-y이고 끝점이 x+y일 때, 다른 영역에 의해 완전히 가려지지 않는 구간의 개수를 구하는 것이다.
따라서 나는 주어지는 입력에 대해 x-y와 x+y를 벡터에 저장했다. 그리고 이를 다음과 같은 순서로 정렬해주었다.
x-y 오름차순x-y가 같다면 x+y가 내림차순
0
~i-1
까지 확인한 x+y의 최대값 보다 i
의 x+y의 값이 더 크다면 구별 가능한 산이므로 ans를 증가해주고 최대값을 변경한다.코드
#include <cstdio> #include <algorithm> #include <queue> using namespace std; typedef pair<int, int> pii; int n, ans = 1, tmp; vector<pii> v; bool comp(pii a, pii b) { if (a.first == b.first) return a.second > b.second; return a.first < b.first; } int main() { scanf("%d", &n); for(int a, b, i = 0; i < n; i++) { scanf("%d %d", &a, &b); v.push_back({a - b, a + b}); } sort(v.begin(), v.end(), comp); tmp = v[0].second; for(int i = 1; i < n; i++) { if (v[i].second > tmp) { tmp = v[i].second; ans++; } } printf("%d", ans); }