oVeron

1.두 개의 수평선을 그었을 때 수평선이 관통하는 직사각형의 수를 구하는 문제이다. 이 문제의 최대 난관은 두 개의 수평선이 같은 직사각형을 지나면 어떻게 할 것인가이다. lazy propagation으로 직사각형의 y좌표의 구간을 1씩 더하는 방법을 써도, 직사각형을 서로 구분할 수 없으므로 문제를 해결할 수 없다. 일단 수평선 하나를 임의로 그어놓고, 또 하나의 수평선을 추가로 긋는 작업을 상상해보자. 이미 그어놓은 수평선과 교차하는 직사각형들은, 수평선을 더 그을 때 중복 처리를 해야만 한다. 그렇다면 수평선과 교차하는 직사각형들을 아예 제거하는 것은 어떨까? 수평선과 교차하는 직사각형들을 제거하여, 위에서 설명한 lazy propagation으로 직사각형의 y좌표의 구간을 1씩 더하는 방법을 사용..

알고리즘/baekjoon 2024. 7. 8. 15:25