링크
문제 요약
2차원 평면에 소들이 존재한다. 소들은 각각 Holsteins(이하 H), Guernseys(이하 G) 중 한군데에 속해있을 때, 직사각형 모양의 펜스를 쳐서 직사각형 내부에 H인 소들만 가두려고 한다. 이때 소들의 최대 마리수와 해당 마리 수를 가두기 위해 필요한 최소한의 넓이를 구하여라. 단, 펜스의 경계에 속한 소도 갇혀있다고 생각하고, 가로 혹은 세로가 0이 되는 경우도 허용된다.
관찰
문제를 읽어보면 금광 문제의 상위호환 문제로 변형이 가능함을 알 수 있다. H인 소를 가치가 1, G인 소를 가치가 -1000 으로 하면 이때 이익이 최대가 되는 직사각형을 찾는 문제와 동일해지기 때문이다. 왜냐하면 G인 소가 들어오는 순간, 해당 직사각형에서 얻을 수 있는 이익은 무조건 음수가 되기 때문에 반드시 최대 직사각형에는 H인 소만 들어있게 된다.
풀이
금광 세그는 이제는 웰노운이기 때문에 다른 블로그에도 자세히 설명이 있을 것이다. 여기서는 간략히 다루도록 하자. 금광 세그의 핵심 아이디어는 최대 연속 부분합을 분할정복으로 구하는 것이다. 해당 값을 구하기 위해서는 아래와 같이 4가지의 값이 필요하다.
- 구간의 합을 저장하는 sum
- 구간의 왼쪽 끝 원소를 무조건 포함하는 최대 연속 부분합 left
- 구간의 오른쪽 끝 원소를 무조건 포함하는 최대 연속 부분합 right
- 구간의 최댓값 ans
이때 왼쪽 구간과, 오른쪽 구간에 대하여 위의 값들을 알게 된다면 현재 2개의 구간을 합친 구간에 대하여도 해당 값들을 계산할 수 있게 된다. 이 과정은 스스로 생각해보도록 하자. 추가적으로 해당 문제에서는 직사각형의 넓이의 최솟값을 구해야 하기 때문에, 최댓값이 같다면 연속 부분합의 길이가 짧은 것을 길이로 저장하면 될 것이다. 따라서 해당 문제를 풀때는 왼쪽, 오른쪽, 전체 최대 연속 부분합의 길이를 저장하는 변수를 추가하면 된다. 시간 복잡도는 금광과 동일한 구조이므로, $O(1000\times N\log{1000})$ 이 된다.