백준 14719 빗물 c++ // 구현, 그리디

https://www.acmicpc.net/problem/14719

1. 의사코드

1. 높이에따라 2차원배열을 만들어줌

2. 값이0인곳에 물이 찰수있는지 탐색함

3. 좌측이 1이있고 우측에 1이있어야 물이찰수있음

빈칸들(0)에 대해 O,X 가능한지 불가능한지 조사함.

2. 전체코드

#include <bits/stdc++.h>

using namespace std;

int Y,X,num, a[504][504],ret;
vector<pair<int,int>> v; //탐색대상위치

int left(int y, int x) {
    if (x < 0) {
        return 0;
    }
    if (a[y][x] == 1) return 1;

    return left(y, x - 1);
}
int right(int y, int x) {
    if (x >= X) {
        return 0;
    }
    if (a[y][x] == 1) return 1;

    return right(y, x + 1);
}

//해당좌표에 빗물이 찰수있는지
int go(int y, int x) {
    //좌측에 1이있고 우측에 1이있으면 빗물찰수있음.

    if (left(y, x) && right(y, x)) return 1;
    return 0;
}


int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> Y>>X;

    for(int i=0;i<X;++i) {
        cin >> num;
        for (int j =Y-1; j>=0; --j) {
            if (num <= 0) break;
            a[j][i] = 1;
            num--;
        }
    }

    for (int i = 0; i < Y; ++i) {
        for (int j = 0; j <X; ++j) {
            if (a[i][j] == 0) {
                v.push_back({ i,j });
            }
            //cout << a[i][j] << " ";
        }//cout << "\n";
    }

    for (auto p : v) {
        if (go(p.first, p.second)) ret++;
    }

    cout << ret;
    return 0;

}

 

3. 개선

최악의경우 :

500칸인경우, 약 500칸에 대해 * 좌,우측에1이있는지 탐색(500번 ->)

250000 -> 가능

 

but, 문제에서 숫자만줬기때문에 더 효율적인 프리가 있다. 약간 그리디 적인듯?

부분최적해가 전체 최적해가 되니까..

4. 의사코드

1. 내 좌측 최대값, 우측최대값을 구함

2. 그중 작은값과 나와의 차이가 물이차는 갯수임.

어려운 문제지요..?? 저는 스택 써서 해결할려다가 피봤습니다.

그냥 단순하게 생각해 봅시다.



11 3 4 5 3 4 5 3 4 5 7이 들어왔다고 쳐 봅시다.



그러면

11 [3] 4 5 3 4 5 3 4 5 7

에서 [3]에는 몇 만큼의 물이 차야 할까요?



[3]의 왼쪽에 있는 것 중 제일 큰 높이를 가지는 건 11입니다.

오른쪽에 있는 것 중에서 제일 큰 높이를 가지는 건 7이네요.



따라서, [3]에는 7만큼의 물이 채워집니다.

이렇게 생각하면 코드가 짧아지고 매우 간결해집니다.

시간복잡도 : 500(각숫자에대해) * 500(좌우탐색) 

똑같네...???