알고스팟 문제 링크: https://algospot.com/judge/problem/read/MINASTIRITH
algospot.com :: MINASTIRITH
미나스 아노르 문제 정보 문제 단 한 번도 함락된 적이 없다는 성채도시 미나스 아노르에는 반지름이 8 킬로미터나 되는 거대한 원형 성벽, 람마스 에코르가 있습니다. 도시 전체를 감싸는 이 거
algospot.com
원모양의 성벽이 있고 시야가 원모양인 초소들이 성벽위에 있을때 성벽을 빈틈없이 감시할 수 있는 초소 갯수의 최솟값을 구하는 문제이다.
먼저 초소위치를 라디안으로 구하고 초소에 감시 반지름과 초소위치를 활용하여 각 초소의 감시범위를 라디안으로 저장한다.
이때 주의할점은 성벽을 [0, 2*pi]범위의 선분으로 표현할 때 시작점(끝점)을 덮는 초소들을 하나씩 순회하면서 먼저 계산하고 나머지 초소들로 남은 성벽범위를 덮어보면서 답을 찾아야 한다는 것이다.
시작점(끝점)을 덮는 초소를 골라 성벽의 나머지 부분을 begin과 end로 표현하고 초소의 시야가 begin전에 시작해서 가장 크게 뻗어나가는 초소를 골라 begin를 갱신하는 방식으로 begin이 end이상이 될때까지 반복한다.
시작점(끝점)을 덮는 초소는 많아야 최대 두개이고, 두 개일때도 둘중에 ranges[i].first가 음수인것은 시야가 시작점으로부터 끝점방향으로 더 길고 ranges[i].second가 2*pi이상인것은 시야가 끝점으로부터 시작점 방향으로 더 길수 밖에 없다는 점에 유의하자.
| #include<iostream> | |
| #include<cmath> | |
| #include<algorithm> | |
| using namespace std; | |
| const double pi = 2.0 * acos(0); | |
| const int INF = 987654321; | |
| int n; | |
| double x[100], y[100], r[100]; | |
| // <초소구역 시작 라디안각도, 초소구역 끝 라디안각도>ranges | |
| pair<double, double>ranges[100]; | |
| // 각 초소에 대한 정보들로 ranges구성 | |
| void convertToRange() { | |
| for (int i = 0; i < n; i++) { | |
| // 초소 위치에 대한 라디안 | |
| double loc = fmod(atan2(y[i], x[i]) + 2 * pi, 2 * pi); | |
| // 초소 감시 범위에 대한 라디안 | |
| double range = 2.0 * asin(r[i] / 2.0 / 8.0); | |
| // 초소 감시범위를 ranges에 저장 | |
| ranges[i] = make_pair(loc - range, loc + range); | |
| } | |
| sort(ranges, ranges + n); | |
| } | |
| // 선형으로 문제를 푸는 함수 전방선언 | |
| int solveLinear(double begin, double end); | |
| // 시작점(끝점)을 완전히 덮는 초소 하나를 원형으로 선택하고 나머지를 선형으로 해결 | |
| int solveCircular() { | |
| int ret = INF; | |
| for (int i = 0; i < n; i++) | |
| if (ranges[i].first <= 0 || ranges[i].second >= 2 * pi) { | |
| // 시작점(끝점)을 완전히 덮는 초소에대한 감시범위를 범위[0, 2pi]로 정규화 | |
| double begin = fmod(ranges[i].second, 2 * pi); | |
| double end = fmod(ranges[i].first + 2 * pi, 2 * pi); | |
| // 나머지를 선형으로 해결했을때 가장 적은 초소를 들이는 경우를 계산 | |
| ret = min(ret, solveLinear(begin, end) + 1); | |
| } | |
| return ret; | |
| } | |
| int solveLinear(double begin, double end) { | |
| int used = 0, idx = 0; | |
| // 범위를 완전히 덮을때까지 반복 | |
| while (begin < end) { | |
| // 선형으로 어디까지 덮었는지 나타냄 | |
| double maxCover = -1; | |
| while (idx < n && ranges[idx].first <= begin) { | |
| // begin전에 시작해서 오른쪽으로 가장 크게 뻗는 초소 선택 | |
| maxCover = max(maxCover, ranges[idx].second); | |
| idx++; | |
| } | |
| // begin전에 시작하는 초소가 없으면 완전히 덮을수 있는 방법 없음 | |
| if (maxCover <= begin)return INF; | |
| // begin전에 시작하는 초고 잘 골랐으면 begin 갱신 | |
| begin = maxCover; | |
| used++; | |
| } | |
| return used; | |
| } | |
| int main() { | |
| int testcase; | |
| cin >> testcase; | |
| while (testcase--) { | |
| cin >> n; | |
| for (int i = 0; i < n; i++) | |
| cin >> y[i] >> x[i] >> r[i]; | |
| convertToRange(); | |
| int result = solveCircular(); | |
| if (result == INF) | |
| cout << "IMPOSSIBLE" << endl; | |
| else | |
| cout << result << endl; | |
| } | |
| } |
코드 원본: https://github.com/sbl133/JongmanBook/blob/main/10.%20Greedy/MINASTIRITH.cpp
GitHub - sbl133/JongmanBook
Contribute to sbl133/JongmanBook development by creating an account on GitHub.
github.com
댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!
reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략1
'Algorithm > algospot' 카테고리의 다른 글
| algospot 알러지가 심한 친구들 (문제 ID: ALLERGY) (0) | 2021.09.02 |
|---|---|
| algospot 게임판 덮기 2 (문제 ID: BOARDCOVER2) (0) | 2021.09.02 |
| algospot 문자열 합치기 (문제 ID: STRJOIN) c++ (0) | 2021.09.01 |
| algospot 도시락 데우기 (문제 ID: LUNCHBOX) c++ (0) | 2021.09.01 |
| algospot 지니어스 (문제 ID: GENIUS) (0) | 2021.08.31 |