해결 전략
정말 아쉽다. 정답에 거의 다 와놓고선, 결국 디테일한 부분을 캐치하지 못해서 서너시간을 해결하지 못한채 전전긍긍했다ㅠㅠ 문제 해결의 퍼센티지를 매기면 초반 10~20분만에 90%를 해놓고서 나머지 10%를 몇 시간동안 못한 것이다ㅠㅠ 좌절감, 실망감이 들긴 하지만, 이를 교훈삼아 좀 더 발전하자.
우선, 문제 해결을 위한 알고리즘을 떠올리는 일은 어렵지 않다. 문제의 입력이 100,000개까지 가능하기 때문에 Naive한 서칭으로는 해결하기 어려움을 어렵지 않게 알 수 있다. Dynamic Programming을 할 상황은 아니고, 그 외 탐색 방법도 굳이 필요치 않아 보인다. 그렇다. Divide & Conquer를 원하는 문제 상황임을 느낄 수 있다(물론, 인터넷을 검색해보면, 이외에 스택이나 세그 트리로도 해결할 수 있다고 한다).
분할한다면 어떻게 하는 것이 좋을까? 학부 알고리즘 수업에서 배웠던 'Maximum Distance Problem'이 떠오른다.
선형 자료구조를 반으로 갈라, 좌측의 답과 우측의 답을 찾아내고, 좌측과 우측에 겹치는 부분의 답을 찾아 세 답 중 Optimal을 반환하자.
배열을 탐색해야하고, 분할된 배열이 따로 떨어지거나 그렇진 않으므로, 병합정렬의 분할 센스를 이용하면 되리라. left와 right를 두고, mid를 계산해서 left~mid, mid+1~right 부분으로 나누자. 이 Idea를 통해 아래와 같은 함수를 떠올릴 수 있다(넓이가 int 범위를 넘어갈 수 있으므로 반환값은 long long으로 처리하자).
long long solve(int left, int right) {
if (left > right) return 0LL;
if (left == right) return (long long)h[left];
long long max_L, max_R, max_M;
int mid = (left + right) / 2;
max_L = solve(left, mid);
max_R = solve(mid + 1, right);
max_M = overlapLR(left, right, mid); // 좌우측에 겹치는 부분의 처리
return max({ max_L, max_R, max_M });
}그렇다. 이 문제는 좌우측에 겹치는 직사각형들 중 최대값을 도출하는 부분이 문제 해결의 핵심인 문제이다. 본인이 이 문제를 몇시간동안 전전긍긍한 이유도 바로 여기에서 온다.
본인이 떠올렸던 중간 부분 처리 방법은 다음과 같다.
1) go_left와 go_right를 두고, 각각 좌측, 우측으로 한 칸씩 확장해가면서 확장 시의 직사각형이 기존의 최대값보다 크면 실제 확장을 진행한다.
2) go_left부터 확인해보고, go_right를 확인한다.
=> 이 2번 과정이 잘못된 접근이었다. 문제의 예제와, 질문 게시판의 대부분의 반례가 좌측부터 처리해도 문제가 없는 예시들이었어서 이를 감지해내지 못했다.
=> 사실 생각해보면, 굳이 좌측부터 갈 이유가 전혀 없다. 만약 예를 들어서 입력이
1 2 3 4 5라고 해보면, left가 1, right가 5일때의 중간 부분 처리에서, 정답인 9를 찾아내지 못한다. 왜냐면, mid인 3을 기준으로 좌측부터 탐색하면 왼쪽의 2로 먼저 확장을 진행해버리기 때문이다.
따라서, 이를 처리하기 위해, 양쪽 중 더 큰 쪽을 찾아 그쪽부터 확장해나가야한다.
그래서, 본인은 좌측 확장 시의 예상 넓이와, 우측 확장 시의 예상 넓이를 미리 계산해, 더 넓이가 큰 쪽으로 확장해나가도록 알고리즘을 수정해서 해결을 시도했다. 그런데, 이것이 계속 통과하지를 않았다. 도무지 왜인지를 모르겠었다(사실 지금도 반례를 찾아내지 못했다).
전전긍긍하다가, "에라이, 기존 방법을 그냥 다 날려버리고, 새로 생각해보자."라는 생각으로 떠오른 Idea는 다음과 같았다.
좌우측 확장할 때, 그냥 높이가 더 큰 쪽으로 확장하면 되지 않겠는가?
기존 직사각형의 넓이가 A라 하면, 양 쪽의 높이가 주어질 때, 무조건 더 높이가 높은 쪽으로 가야 넓이가 최소한 유지를 하거나, 더 넓어진다. 높이가 낮은쪽으로 가면 그 확장 방향 반대쪽은 고정이니 무조건 넓이가 작아지기 때문이다.
이 간단한 방법을 찾아내는데 2~3시간이나 걸린 것이다ㅠㅠ 이 방법으로 풀이 시도를 할 경우, 확장을 고려하는 방향의 반대 방향이 끝에 도달했을 때를 예외로 처리해주는 작업만 해주면 가볍게 문제를 해결할 수 있다.
본인이 두번째 시도에서 설계했던 알고리즘이 이를 왜 커버하지 못하는지는 사실 아직도 잘 모르겠다. 어딘가 빵꾸가 뚫린다는 것인데, 솔직히 글을 쓰는 지금도 잘 모르겠다. 좌우측 확장 시의 넓이를 비교해 더 넓은쪽으로 진행하는 것이, 높이가 더 높은쪽으로 진행하는 것과 수학적으로 차이가 있을까? 아마 동일값 처리 과정에서 뭔가 빵꾸가 나는게 아닐까 싶긴 한데, 이도 확실친 않다. 백준의 테스트 케이스를 직접 받아보지 않고선 잘 모르겠다.
그러나, 하나 확실한 점은 있다.
알고리즘 구현 과정이 무언가 복잡하고 예외가 많으면 그 구현은 필패이다.
한 가지 반성을 하자면, 풀이를 시도할 때, "아, 굳이 넓이 비교를 하지 말고 좀 더 간단하게 판단할 수 있는 방법은 없을까?"라고 고민해보지 않은 것은 분명 PS 연습에서 좋지 못한 습관이다. 이를 고쳐나가도록 하자.
아래는 코드이다.
#include <iostream>
#include <algorithm>
// BOJ - 6549 Biggest Rectangle in Histogram
#define MAX_SIZE 100000
using namespace std;
int h[MAX_SIZE + 1];
long long overlapLR(int left, int right, int mid) {
int go_left = mid, go_right = mid, min_h = h[mid];
long long max_area = h[mid];
while (go_left > left || go_right < right) {
if (go_right < right && (go_left == left || h[go_left - 1] < h[go_right + 1])) {
go_right++;
min_h = min(min_h, h[go_right]);
}
else {
go_left--;
min_h = min(min_h, h[go_left]);
}
max_area = max(max_area, (long long)min_h * (long long)(go_right - go_left + 1));
}
return max_area;
}
long long solve(int left, int right) {
if (left > right) return 0LL;
if (left == right) return (long long)h[left];
long long max_L, max_R, max_M;
int mid = (left + right) / 2;
max_L = solve(left, mid);
max_R = solve(mid + 1, right);
max_M = overlapLR(left, right, mid);
return max({ max_L, max_R, max_M });
}
int main(void) {
int n;
while (1) {
cin >> n; if (n == 0) break;
for (int i = 1; i <= n; i++) cin >> h[i];
cout << solve(1, n) << '\n';
}
return 0;
}한편, 백준 1725번 - 히스토그램 문제도 똑같은 알고리즘 및 코드로 해결할 수 있다. 테스트케이스로 확인하느냐, 아니냐의 차이일 뿐이다.
