Toivoa 님께서 올려주신 에디토리얼에 덧붙여, O(n^2)의 쉬운 풀이를 제시해 봅니다. 이 문제에 알려진 더 좋은 풀이가 존재하긴 하는데, 제가 남들에게 설명할 만큼 충분히 이해하고 있지는 않은 것 같습니다.
사실 이 문제를 O(n^2)에 푼다고 하면 정말 간단해집니다.
직사각형의 밑변이 [i,j] 까지의 구간을 포함해야 한다고 칩시다. 이 때의 직사각형의 밑변의 길이는 (j - i + 1) 이고, 높이는 ( min(end[k] where k in [i, j]) - max(start[k] where k in [i, j]) ) 인 직사각형이 그러한 것들 중 최대가 될 것입니다.
그래서 O(n^2) 루프를 통하여 i, j를 반복합니다. 윗 부분의 높이 중 최소값과 아랫 부분의 높이 중 최대값은 j가 반복되면서 차례로 갱신할 수 있습니다. 다시 말하면, min(end[k] where k in [i, j + 1]) = min( min(end[k] where k in [i, j]), end[j + 1]) 과 같이 설명할 수 있지요.
Being
Toivoa 님께서 올려주신 에디토리얼에 덧붙여, O(n^2)의 쉬운 풀이를 제시해 봅니다. 이 문제에 알려진 더 좋은 풀이가 존재하긴 하는데, 제가 남들에게 설명할 만큼 충분히 이해하고 있지는 않은 것 같습니다.
사실 이 문제를 O(n^2)에 푼다고 하면 정말 간단해집니다.
직사각형의 밑변이 [i,j] 까지의 구간을 포함해야 한다고 칩시다. 이 때의 직사각형의 밑변의 길이는 (j - i + 1) 이고, 높이는 ( min(end[k] where k in [i, j]) - max(start[k] where k in [i, j]) ) 인 직사각형이 그러한 것들 중 최대가 될 것입니다.
그래서 O(n^2) 루프를 통하여 i, j를 반복합니다. 윗 부분의 높이 중 최소값과 아랫 부분의 높이 중 최대값은 j가 반복되면서 차례로 갱신할 수 있습니다. 다시 말하면, min(end[k] where k in [i, j + 1]) = min( min(end[k] where k in [i, j]), end[j + 1]) 과 같이 설명할 수 있지요.
16년 전