H번 문제는 제출 수로는 중간에 위치한 문제입니다. 앞의 네 문제가 어느 정도 쉬운 문제들이었다면, H번은 이러한 문제들을 다 풀고 제일 먼저 시도해볼 수 있는 문제라 할 수 있겠습니다. 그러나 역으로, H번은 정답률이 낮은 순서로는 세 번째의 문제입니다. 즉 이 문제는 쉬워 보이지만 뭔가 한가지를 놓치기가 쉬운 문제라 할 수 있겠습니다.
문제를 살펴보면, 두 직사각형의 각 변이 축에 평행하며, 서로 겹치지 않아야 한다는 조건이 있습니다. 바로 이 조건 때문에 이 문제가 쉬워집니다. 서로 겹치지 않는 두 직사각형은 어떻게 배치될까요? 이런 저런 경우를 생각해보면, 가능한 배치는 日자 형태뿐임을 알 수 있습니다. 즉, x축(또는 y축)과 평행한 어떤 선을 기준으로 평면을 둘로 나눴을 때, 두 직사각형은 각각의 평면에 위치하게 되는 것입니다.
그렇다면 이러한 기준선은 어떻게 찾을 수 있을까요? 왼쪽 사각형의 오른쪽 변과 오른쪽 사각형의 왼쪽 변 사이에 위치할 수 있을 것입니다. 따라서 이러한 선을 한 쪽 사각형에 붙어 있는 것으로 생각할 수 있습니다. 편의상 왼쪽 사각형에 붙어 있다고 합시다. 그러면 각 점의 x좌표를 살펴보면서, [제일 왼쪽 점 ~ 현재 살펴보고 있는 점] 의 범위에서 사각형을 하나 만들고, 나머지 점들을 포함하는 사각형을 하나 만들면 됩니다. 점들을 정렬해두고, [제일 왼쪽 점 ~ i번째 점] 의 범위의 최소/최대 i값을 저장해두고, [i번째 점 ~ 제일 오른쪽 점] 의 범위에서도 최소/최대 i값을 저장해두면 이러한 사각형의 넓이를 쉽게 구할 수 있습니다. 이러한 기준선이 y축이 아니라 x축에 평행할 수 있기 때문에, x축과 y축을 반대로 생각하여 위의 과정을 한번 더 반복해야 합니다.
하지만.. 또다른 조건 때문에 단순히 위의 방법만으로는 해결할 수 없습니다. 두 직사각형의 변이 서로 겹치는 경우에는 어떻게 해야 할까요? 즉, 우리가 잡은 기준선 상에 여러 점들이 있다면, 각각의 점들은 어느 쪽 사각형에 포함시켜야 할까요? 단순히 한쪽 사각형, 위의 방법처럼 왼쪽 사각형에 포함시켜서는 최적해를 보장할 수 없습니다. 아래의 그림을 살펴보시면 이해하실 수 있을 겁니다. (*주 : 필자의 사정 때문에 당분간은 그림이 착한 사람 눈에만 보입니다)
따라서 기준선 상의 점들을 왼쪽 사각형과 오른쪽 사각형에 적당히 분배해주어야 합니다. 그런데 가만히 생각해보면, 한 쪽 사각형에 포함되는 점의 y좌표의 최대값은, 다른 쪽 사각형에 포함되는 점의 y좌표의 최소값보다 작아야 합니다. 예를 들어, 왼쪽 사각형에 y좌표가 [1, 3, 5]인 점이 포함되고, 오른쪽 사각형에 y좌표가 [2, 4, 6, 8]인 점이 포함된다면, 이는 왼쪽 사각형에 [1, 2, 3, 4, 5]인 점들을, 오른쪽 사각형에 [6, 8]인 점들을 포함시키는 경우로 생각할 수 있다는 것입니다. 즉, 기준선에 수직인 또다른 기준선을 그어, 한쪽 점들은 왼쪽 사각형에, 다른 쪽 점들을 오른쪽 사각형에 포함시켜보면 됩니다. 이 경우에는 기준선의 윗쪽 점들도 왼쪽 사각형에 포함될 수 있으며, 아랫쪽 점들도 왼쪽 사각형에 포함될 수 있습니다. 따라서 두 가지의 경우를 모두 따져봐야 합니다.
말이 길어졌는데.. 아래와 비슷한 코드로 위의 알고리즘을 구현할 수 있습니다.
점들을 정렬한다(x좌표를 기준으로 하고, x좌표가 같은 경우에는 y좌표를 기준으로 한다).
점들을 하나씩 살펴보면서, i번째 점을 기준점으로 삼는다.
A = i번째 점보다 왼쪽에 위치한 점들.
B = i번째 점보다 오른쪽에 위치한 점들.
C = i번째 점과 x좌표가 같으며, y좌표는 같거나 작은 점들.
D = i번째 점과 x좌표가 같으며, y좌표는 큰 점들.
A & C에서 사각형을 하나 구하고, B & D에서 사각형을 하나 구한다.
A & D에서 사각형을 하나 구하고, B & C에서 사각형을 하나 구한다.
x축과 y축을 반대로 생각하여 위의 과정을 다시 한 번 반복한다.
위에서 사각형을 구한다는 말의 의미는, 각 사각형의 넓이를 구해보고 더 큰 넓이가 현재 최적해보다 작다면 갱신시킨다는 의미입니다. 이를 구현하면 정렬에 O(N log N)의 시간이 들고, 기준점을 삼는데 O(N)의 시간이 듭니다. 점들을 분류하여 사각형을 구해보는 것은 (구현은 다소 복잡할 수 있겠지만) O(1)에 가능합니다. 혹 자료구조나 STL에 능숙하신 분이라면 이를 활용하여 깔끔하게 O(log N)만에 구현할 수도 있겠습니다. 설명이 다소 복잡했는데, 아래에 첨부될 코드를 참고하시면 도움이 될 것으로 생각합니다.
끝으로 이 문제를 성공적으로 풀어내신 분들께 아래의 문제를 추천합니다. 조금 더 다양한 경우를 고려해야 할 것이라 생각합니다. http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3282
lewha0
H번 문제는 제출 수로는 중간에 위치한 문제입니다. 앞의 네 문제가 어느 정도 쉬운 문제들이었다면, H번은 이러한 문제들을 다 풀고 제일 먼저 시도해볼 수 있는 문제라 할 수 있겠습니다. 그러나 역으로, H번은 정답률이 낮은 순서로는 세 번째의 문제입니다. 즉 이 문제는 쉬워 보이지만 뭔가 한가지를 놓치기가 쉬운 문제라 할 수 있겠습니다.
문제를 살펴보면, 두 직사각형의 각 변이 축에 평행하며, 서로 겹치지 않아야 한다는 조건이 있습니다. 바로 이 조건 때문에 이 문제가 쉬워집니다. 서로 겹치지 않는 두 직사각형은 어떻게 배치될까요? 이런 저런 경우를 생각해보면, 가능한 배치는 日자 형태뿐임을 알 수 있습니다. 즉, x축(또는 y축)과 평행한 어떤 선을 기준으로 평면을 둘로 나눴을 때, 두 직사각형은 각각의 평면에 위치하게 되는 것입니다.
그렇다면 이러한 기준선은 어떻게 찾을 수 있을까요? 왼쪽 사각형의 오른쪽 변과 오른쪽 사각형의 왼쪽 변 사이에 위치할 수 있을 것입니다. 따라서 이러한 선을 한 쪽 사각형에 붙어 있는 것으로 생각할 수 있습니다. 편의상 왼쪽 사각형에 붙어 있다고 합시다. 그러면 각 점의 x좌표를 살펴보면서, [제일 왼쪽 점 ~ 현재 살펴보고 있는 점] 의 범위에서 사각형을 하나 만들고, 나머지 점들을 포함하는 사각형을 하나 만들면 됩니다. 점들을 정렬해두고, [제일 왼쪽 점 ~ i번째 점] 의 범위의 최소/최대 i값을 저장해두고, [i번째 점 ~ 제일 오른쪽 점] 의 범위에서도 최소/최대 i값을 저장해두면 이러한 사각형의 넓이를 쉽게 구할 수 있습니다. 이러한 기준선이 y축이 아니라 x축에 평행할 수 있기 때문에, x축과 y축을 반대로 생각하여 위의 과정을 한번 더 반복해야 합니다.
하지만.. 또다른 조건 때문에 단순히 위의 방법만으로는 해결할 수 없습니다. 두 직사각형의 변이 서로 겹치는 경우에는 어떻게 해야 할까요? 즉, 우리가 잡은 기준선 상에 여러 점들이 있다면, 각각의 점들은 어느 쪽 사각형에 포함시켜야 할까요? 단순히 한쪽 사각형, 위의 방법처럼 왼쪽 사각형에 포함시켜서는 최적해를 보장할 수 없습니다. 아래의 그림을 살펴보시면 이해하실 수 있을 겁니다. (*주 : 필자의 사정 때문에 당분간은 그림이 착한 사람 눈에만 보입니다)
따라서 기준선 상의 점들을 왼쪽 사각형과 오른쪽 사각형에 적당히 분배해주어야 합니다. 그런데 가만히 생각해보면, 한 쪽 사각형에 포함되는 점의 y좌표의 최대값은, 다른 쪽 사각형에 포함되는 점의 y좌표의 최소값보다 작아야 합니다. 예를 들어, 왼쪽 사각형에 y좌표가 [1, 3, 5]인 점이 포함되고, 오른쪽 사각형에 y좌표가 [2, 4, 6, 8]인 점이 포함된다면, 이는 왼쪽 사각형에 [1, 2, 3, 4, 5]인 점들을, 오른쪽 사각형에 [6, 8]인 점들을 포함시키는 경우로 생각할 수 있다는 것입니다. 즉, 기준선에 수직인 또다른 기준선을 그어, 한쪽 점들은 왼쪽 사각형에, 다른 쪽 점들을 오른쪽 사각형에 포함시켜보면 됩니다. 이 경우에는 기준선의 윗쪽 점들도 왼쪽 사각형에 포함될 수 있으며, 아랫쪽 점들도 왼쪽 사각형에 포함될 수 있습니다. 따라서 두 가지의 경우를 모두 따져봐야 합니다.
말이 길어졌는데.. 아래와 비슷한 코드로 위의 알고리즘을 구현할 수 있습니다.
점들을 정렬한다(x좌표를 기준으로 하고, x좌표가 같은 경우에는 y좌표를 기준으로 한다).
점들을 하나씩 살펴보면서, i번째 점을 기준점으로 삼는다.
A = i번째 점보다 왼쪽에 위치한 점들.
B = i번째 점보다 오른쪽에 위치한 점들.
C = i번째 점과 x좌표가 같으며, y좌표는 같거나 작은 점들.
D = i번째 점과 x좌표가 같으며, y좌표는 큰 점들.
A & C에서 사각형을 하나 구하고, B & D에서 사각형을 하나 구한다.
A & D에서 사각형을 하나 구하고, B & C에서 사각형을 하나 구한다.
x축과 y축을 반대로 생각하여 위의 과정을 다시 한 번 반복한다.
위에서 사각형을 구한다는 말의 의미는, 각 사각형의 넓이를 구해보고 더 큰 넓이가 현재 최적해보다 작다면 갱신시킨다는 의미입니다. 이를 구현하면 정렬에 O(N log N)의 시간이 들고, 기준점을 삼는데 O(N)의 시간이 듭니다. 점들을 분류하여 사각형을 구해보는 것은 (구현은 다소 복잡할 수 있겠지만) O(1)에 가능합니다. 혹 자료구조나 STL에 능숙하신 분이라면 이를 활용하여 깔끔하게 O(log N)만에 구현할 수도 있겠습니다. 설명이 다소 복잡했는데, 아래에 첨부될 코드를 참고하시면 도움이 될 것으로 생각합니다.
끝으로 이 문제를 성공적으로 풀어내신 분들께 아래의 문제를 추천합니다. 조금 더 다양한 경우를 고려해야 할 것이라 생각합니다.
http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3282
17년 전