[백준][C++] 14719 빗물

www.acmicpc.net/problem/14719

14719번: 빗물

 

 

 

알고리즘 종류

    - 구현

 

 

사고 과정

    - 빗물이 고인다는 것은 양쪽에 벽이 있다는 것을 의미한다. 따라서, 벽이 나타나면, 같은 행에서 다른 벽이 있는지 확인하고 차이 만큼 빗물이 고인다.

 

 

 

구현(C++)

#include <iostream>
 
using namespace std;
 
int H, W;
int answer = 0;
int mat[501][501];
 
void solution(){
    
    for(int i=0; i<H; i++){
        for(int j=0; j<W; j++){
            if(!mat[i][j]) continue;
            
            int idx = j;
            while(!mat[i][++idx] && idx<W);
            if(idx>=W) break;
            answer += idx - j - 1;
            j = idx - 1;
            
        }
    }
 
    cout << answer;
}
 
 
int main(void){
    
    cin >> H >> W;
    
    int blocks;
    for(int i=0; i<W; i++){
        cin >> blocks;
        for(int j=H-1; j>=H-blocks; j--){
            mat[j][i] = 1;
        }
    }
    
    solution();
}
 

 

 

 

시행착오