[알고리즘 문제] 백준14719 - 빗물

www.acmicpc.net/problem/14719

14719번: 빗물

예전에 모 회사 코딩테스트에 나왔던 문제인데 그떄 못풀었습니다. 어떻게풀까 고민만 하다가 끝난 문제...

 

해결방법은 각열에 빗방울을 떨어뜨려보면서 넘치지 않으면 정답에 더해주었습니다. 여기서 넘치지 않는것을 검사하는 방법은 각 열의 좌우로 빗방울의 높이보다 같거나 더 높은 벽이 있으면 됩니다. 그리고 빗방울을 하나씩 더해주는 것보다 각 열에서 높이가 넘치지 않을 정도의 최대높이부터 하나씩 빼주면서 검사하면 한번에 각 열의 빗방울 최대높이를 구할 수 있습니다.

 

그리고 첫번째, 마지막 열은 검사해주지 않는데 이는 첫/마지막 열에 벽은 있어도 되지만 물이 있으면 의미가 없이 때문입니다. 이런 경우는 예제에서 확인할 수 있습니다.

 

4 4

3 0 1 4

 

의 경우 높이가 4이기 때문애 2열(0)의 경우 4,3,2,1높이의 물이 담겼을 때 좌우로 이보다 같거나 높은 벽이 있는지 검사합니다. 2열의 경우 3, 3열의 경우 2 물높이가 허용됩니다.

 

#include <iostream>

using namespace std;

int main()
{

    int height, width;
    cin >> height >> width;

    int arr[501];

    for (int i = 0; i < width; i++)
    {
        cin >> arr[i];
    }

    int ans = 0;

    for (int i = 1; i < width - 1; i++)
    {
        for (int h = height - arr[i]; h > 0; h--)
        {
            bool leftCheck = false;
            for (int left = 0; left < i; left++) // 왼쪽검사
            {
                if (arr[left] >= h + arr[i])
                {
                    leftCheck = true;
                    break;
                }
            }

            bool rightCheck = false;
            for (int right = i + 1; right < width; right++) // 오른쪽 검사
            {
                if (arr[right] >= h + arr[i])
                {
                    rightCheck = true;
                    break;
                }
            }
            if (leftCheck && rightCheck)
            {
                ans += h;
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}