백준 14719 - 빗물, C++

14719 : www.acmicpc.net/problem/14719

#include <iostream>
#include <algorithm>
using namespace std;

int w, h, l, r, answer = 0;
int height[501];

int main(){
    scanf("%d %d", &h, &w);

    for(int i = 0; i < w; i++)
        scanf("%d", &height[i]);

    for(int i = 1; i < w-1; i++) {
        l = 0;
        r = 0;
        for (int j = 0; j < i; j++)
            l = max(l, height[j]);
        
        for (int j = i + 1; j < w; j++)
            r = max(r, height[j]);
        
        answer += max(0, min(l, r) - height[i]);
    }
    printf("%d\n", answer);
}

---

 1초의 시간이 주어지는데 탐색할 범위가 500이기 때문에 O(n^3)이 1억이 살짝 넘어 완전 탐색을 통해서 풀이할 수 있었습니다. (실제로 O(n^2) 정도)

 

 맨 처음과 끝은 고려할 필요 없고 중간에 있는 부분만 고려하면 되고 문제 풀이 방식은 i 번째에서 얼마나 물을 가져올 수 있는가가 핵심입니다. i 번째에서 물을 가져올 수 있는 최대 양은 좌, 우를 비교했을 때 제일 높은 부분 (그래야 물을 담을 수 있으니깐)을 구한 뒤 이중 낮은 값을 가져와 i의 높이와 비교하면 됩니다.

answer += min(l, r) - height[i];
answer += max(0, min(l, r) - height[i]);

 그리고 출력 변수에 값을 더해야 하는데 위 코드대로 하니 백준 2번째 예제에서 값이 다르게 나옵니다. 이건 i 번째가 좌/우보다 높을 경우나타나는 현상으로 값을 빼버리기 때문에 정답보다 값이 적게 나옵니다. 그래서 0과의 비교 후 값을 대입해야 정답을 가져올 수 있습니다.