[C++] 백준 14719 : 빗물

문제

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

 

 

풀이

  내 아이디어로 푸는 것을 실패해서 문제 푸는 아이디어를 얻을 때 다른 기술 블로그를 참고했다. https://hwan-shell.tistory.com/276 이 블로그의 아이디어를 참고하여 구현했다.

 

 

#include <iostream>
using namespace std;

int h, w, ans;
int block[501];

int left_h(int i){
    int m = 0;
    for(int j=0; j<=i; j++){
        if(m < block[j]) m = block[j];
    }
    return m;
}

int right_h(int i){
    int m = 0;
    for(int j = i; j<w; j++){
        if(m < block[j]) m = block[j];
    }
    return m;
}

int main()
{
    cin >> h >> w;
    for(int i=0; i<w; i++){
        cin >> block[i];
    }
    
    for(int i=1; i<w-1; i++){
        int l = left_h(i);
        int r = right_h(i);
        
        if(l > r){
            ans += r - block[i];
        }
        else{
            ans += l - block[i];
        }
    }
    
    cout << ans << "\n";
    return 0;
}

 

 

메모

  처음에 생각했던 방법은 기준 벽보다 더 높은 높이의 벽이 나타나면 그 가운데 구간에 물을 채우고 기준벽을 갱신하고.. 이런 방법을 생각했다. 그런데 잘못된 답이 나오는 예외가 발생하고..ㅜㅜ 그래서 풀이를 찾아봤는데 생각보다 너무너무 쉬워서 놀랐다.. 리프레쉬? 좀 하고 다시 풀어봤으면 혼자서 풀 수 있었던 문제인 것 같아 아쉽다!

 

당장 문제가 안 풀릴 때 계속 고민하지 말고 다음 날에 다시 생각해보기! ^*^