알고리즘
2020. 10. 21.
[BOJ] 10167번: 금광
10167번: 금광 첫 줄에는 금광들의 개수 N (1 ≤ N ≤ 3,000)이 주어진다. 이어지는 N개의 줄 각각에는 금광의 좌표 (x,y)를 나타내는 음이 아닌 두 정수 x와 y(0 ≤ x,y ≤ 109), 그리고 금광을 개발하면 얻게 되는 이익 www.acmicpc.net 사용 알고리즘 plane sweeping segment tree 시간 복잡도 O($N^2 log N$) 풀이 N이 최대 3000이기 때문에 시간 복잡도가 최대 O($N^2 logN$)인 알고리즘을 사용하여야 한다. 금광들을 직사각형 모양의 영역으로 묶어 이익을 확인할 경우, 금광들의 가장 좌측 상단에 있는 금광과 가장 우측 하단에 있는 금광을 기준으로 직사각형을 만들 수 있다. 따라서 금광들의 위치만으로 분할정복을 통해 구간의 합을..
