문제 링크
- http://icpc.me/11750
문제 출처
- 2015 Tsukuba Regional D번
사용 알고리즘
- 그리디
- 스위핑
시간복잡도
- $O(N^2 \log N)$
풀이
각 사람의 시야는 구간으로 표현할 수 있습니다.
선형인 경우의 풀이를 먼저 생각해보면, 끝점 기준으로 정렬을 한 다음 스위핑을 하면서 최대한 뒤쪽에 시계를 배치하는 방식의 그리디로 풀 수 있습니다. 이 풀이는 $O(N \log N)$입니다.
이 문제는 선형이 아니고 원형입니다. N도 최대 1000으로 꽤 작습니다.
이쯤 되면 다들 예상했겠지만, 선형일 때의 풀이를 N번 반복해주면 문제를 풀 수 있습니다.
원형 구조인 것이 싫으니까, 시작점으로 잡을 구간 하나를 선택해서 선형으로 펴주면 됩니다.
총 N번의 시도에서 가장 시계를 적게 썼을 때의 개수를 출력해주면 됩니다.
전체 코드
1 |
|