[Algorithm]Baekjoon 14719번 : 빗물

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

14719번: 빗물

 
int h, w;
int blocks[500];                                                                                                                                                                                  
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> h >> w;
 
    for (int i = 0; i < w; ++i)
    {
        cin >> blocks[i];
    }
 
    int left = 0;
    int right = w - 1;
    int leftMax = blocks[left];
    int rightMax = blocks[right];
    int answer = 0;
 
    while (left < right)
    {
        leftMax = max(leftMax, blocks[left]);
        rightMax = max(rightMax, blocks[right]);
 
        if (leftMax > rightMax)
        {
            answer += rightMax - blocks[right];
            --right;
        }
        else
        {
            answer += leftMax - blocks[left];
            ++left;
        }
    }
 
    cout << answer;
}

 

한번쯤 풀어보길 권장하는 문제.

여러방법 풀이가 있는데, 꼭 투포인터로 푸는 방법을 한번쯤은 풀어봐야한다.

인풋최대값이 작아서 n^2로도 통과할 순 있다.

그러나 투포인터를 이용하여 n번으로도 풀이가 가능하다.

n^2 과 n번은 하늘과 땅차이니, n번풀이를 아는게 좋을거라 생각한다.

 

일단 앞서말했듯이 투 포인터를 이용한다.

각 포인터 left, right는 주어진 blocks의 양끝에서 시작해서 조건에 따라 가운데로 이동한다. (left는 ++, right --)

각 차례마다 각 방향에서의 최대값들을 계속 저장한다.

이후 반복문을 수행하는데, 왼쪽최대값이 오른쪽최대값보다크다면, 오른쪽인덱스의 빗물의 양을 결과에 누적시킨다.

오른쪽최대값이 더 크다면 반대로 해주면 된다.

그러면 끝.

 

그러면 왜? 이게 가능할까.

빗물을 값에 누적시키려면, 해당 인덱스기준으로 왼쪽벽최대큰값과 오른쪽벽 최대큰값을 구한 후, 두 값중 작은값 - blocks[i]를 해야한다. 한쪽벽이 아무리 크더라도, 나머지 한쪽벽이 작으면 최대 작은벽만큼만 누적시킬 수 있다.

보통 여기까지는 어찌저찌 생각할 수 있다.

그러면 각 인덱스마다 왼쪽벽최대값과 오른쪽벽 최대값을 어떻게 구할것인가?

여기서 n^2으로 푸느냐, n으로 푸느냐가 결정된다.

각 인덱스마다 왼,오른쪽을 탐색하면 n^2이 된다.

하지만 위의 풀이처럼 투포인터로 계속 최대값들을 들고있으면 n번으로 가능하다.