[백준] 14719번 빗물

 

 

문제

 

소스코드

#include<iostream>
#include<vector>
 
bool CheckAbleBlock(std::vector<int>& ground, int index) {
    //왼쪽 오른쪽 방향키
    int lhs = index - 1;
    int rhs = index + 1;
    bool left{ false }, right{ false };
    while (true) {
 
        //범위 밖이면 flase
        if (lhs < 0 || rhs >= ground.size())return false;
        //둘다 만족하면 true
        if (left && right)return true;
 
        //더 큰 값이 있는지 찾기 위해 감소(왼쪽)
        if (ground[lhs] <= ground[index]) {
            --lhs;
        }
        else {
            left = true;
        }
 
        //더 큰 값이 있는지 찾기 위해 증가(오른쪽)
        if (ground[rhs] <= ground[index]) {
            ++rhs;
        }
        else {
            right = true;
        }
    }
}
 
int main() {
    int H{}, W{}, totalAdd{};
    std::cin >> H >> W;
    std::vector<int> ground;
    for (int i = 0; i < W; ++i) {
        int n{};
        std::cin >> n;
        ground.emplace_back(n);
    }
 
    for (int j = 0; j < H; ++j) {
        for (int i = 0; i < W; ++i) {
 
            //왼쪽과 오른쪽을 탐색해서 둘다 true가 나오면 삽입
            if (CheckAbleBlock(ground, i)) {
                //gruond 값 증가
                ground[i]++;
                //토탈  값 증가
                totalAdd++;
            }
        }
    }
 
    std::cout << totalAdd << "\n";
}
 
 

후기

이 문제를 해결하기 위한 방법은 Two Pointer(투 포인터)이다. 투 포인터란 두 개의 포인터를 가지고 탐색하는 알고리즘이다.

 

먼저 H와 W 크기만큼 반복문을 돌면서 각 블록에 빗물이 쌓일 수 있는지 체크를 하면서 블록에 빗물이 쌓일 수 있는지 체크하기 위해 CheckAbleBlock() 함수를 통해 체크를 한다.

 

해당 함수에 들어오게 되면 먼저 해당하는 블록 Index에서 lhs(왼쪽), rhs(오른쪽) 두 개의 포인터를 가지고 탐색을 시작한다.  그 후 각자 탐색을 시작하면서 현재 블록보다 더 큰 블록이 있다면 bool 값(left, right)에 true를 아니라면 더 큰 게 있는지 체크하면서 증가 감소를 범위 안에 있을 때까지 반복한다.

 

문제의 구현보다는 어떻게 접근할 것인가 하는 부분에서 많은 시간을 소비했다.

해결하는데 걸린 시간: 30분

 

출처

문제 링크: 14719번: 빗물 (acmicpc.net)

 

관련 글(투 포인터)

[온라인 코딩/탐색(Search)] - [백준] 1806번 부분합

[온라인 코딩/탐색(Search)] - [백준] 2018번 수들의 합 5

[온라인 코딩/탐색(Search)] - [백준] 2003번 수들의 합 2