💕
후원
[BOJ] 10167. 금광
10167번: 금광 첫 줄에는 금광들의 개수 N (1 ≤ N ≤ 3,000)이 주어진다. 이어지는 N개의 줄 각각에는 금광의 좌표 (x,y)를 나타내는 음이 아닌 두 정수 x와 y(0 ≤ x,y ≤ 109), 그리고 금광을 개발하면 얻게 되는 이익 www.acmicpc.net 어떤 2차원 그래프에서, 가능한 직사각형 모양의 범위 내부에 있는 정점의 값의 합 중 최댓값을 구하는 문제입니다. 좌표 x, y의 범위는 (0 ≤ x,y ≤ 10^9)인데, 정점의 개수는 최대 3000개이므로 좌표 압축을 사용해 (0 ≤ x,y < 3000) 으로 만들어줍니다. 시간 제한은 3초이므로 O(N^2logN) 으로 해결하면 됩니다. 일반적으로 사각형을 선택하는 기준은 세로 선 두 개, 가로 선 두 개로 O(N^4)라고 생..
2021. 2. 20.