algospot 미나스 아노르 (문제ID: MINASTIRITH) c++

알고스팟 문제 링크: https://algospot.com/judge/problem/read/MINASTIRITH

algospot.com :: MINASTIRITH

원모양의 성벽이 있고 시야가 원모양인 초소들이 성벽위에 있을때 성벽을 빈틈없이 감시할 수 있는 초소 갯수의 최솟값을 구하는 문제이다.

먼저 초소위치를 라디안으로 구하고 초소에 감시 반지름과 초소위치를 활용하여 각 초소의 감시범위를 라디안으로 저장한다.

이때 주의할점은 성벽을 [0, 2*pi]범위의 선분으로 표현할 때 시작점(끝점)을 덮는 초소들을 하나씩 순회하면서 먼저 계산하고 나머지 초소들로 남은 성벽범위를 덮어보면서 답을 찾아야 한다는 것이다.

시작점(끝점)을 덮는 초소를 골라 성벽의 나머지 부분을 begin과 end로 표현하고 초소의 시야가 begin전에 시작해서 가장 크게 뻗어나가는 초소를 골라 begin를 갱신하는 방식으로 begin이 end이상이 될때까지 반복한다.

시작점(끝점)을 덮는 초소는 많아야 최대 두개이고, 두 개일때도 둘중에 ranges[i].first가 음수인것은 시야가 시작점으로부터 끝점방향으로 더 길고 ranges[i].second가 2*pi이상인것은 시야가 끝점으로부터 시작점 방향으로 더 길수 밖에 없다는 점에 유의하자.

 

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/10.%20Greedy/MINASTIRITH.cpp

GitHub - sbl133/JongmanBook

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략1