[구현] 빗물(14719)(C++)

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

14719번: 빗물

 

1. 문제 개요

 

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.

비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

 

 

2. 입출력

 

 

 

3. 문제 풀이

 

처음에는 빗물이 고일 수 있는 조건이 무엇이 있을까 생각을 해보고 그 조건이 만족되면 빗물이 고이는 넓이를 총합에 더해주면 되겠구나!하고 생각했다. 그러나 1%에서 바로 통과되지 못하고 실패가 떴다.

 

왜 실패가 뜨지? 해서 질문탭에서 반례를 찾아보던 중, 내 코드에서는 오답이 나오는 반례 몇가지를 찾아서 그 부분을 고쳤다.

그래도 똑같이 1%에서 실패가 떴다.

 

그러다가 질문탭에서 다음과 같은 글을 읽었다.

이 분의 글을 보니 딱 감이 왔다...

바로 맞았다.

 

 

4. 전체 코드

 

-  처음에 시도했던 코드: 실패했다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void) {
    int H, W;
    vector<int> v;
    scanf("%d%d",&H,&W);
    v.push_back(0);
    
    for(int i=0;i<W;i++) {
        int temp;
        scanf("%d",&temp);
        v.push_back(temp);
    }
    v.push_back(0);
    int startIndex = 0, lastIndex=0, sum = 0;
    bool isStart = false;
    
    for(int i=0;i<v.size();i++){
        if((!isStart)&&(v[i]>v[i+1])){
            isStart = true;
            startIndex = i;
        } else if((isStart)&&(v[i]>v[i+1])){
            int max = v[i];
            lastIndex = i;
            if(v[lastIndex]<v[startIndex]) {
                for(int j=i+1;j<v.size();j++){
                    if(v[j]>max){
                        max = v[j];
                        lastIndex = j;
                    }
                }
            }
            for(int j=startIndex+1;j<lastIndex;j++) {
                isStart = false;
                sum = (min(v[startIndex],v[lastIndex])-v[j]<0)? sum:sum+(min(v[startIndex],v[lastIndex])-v[j]);
            }
            i = lastIndex;
            if(v[i]>v[i+1]) {
                isStart = true;
                startIndex = i;
            }
        }
    }
    printf("%d",sum);
}

 

- 두 번째 시도했던 코드

#include <iostream>
#include <algorithm>

using namespace std;

int main(void) {
    int H, W, list[502], sum = 0;
    scanf("%d%d",&H,&W);
    
    list[0] = 0;
    for(int i=1;i<=W;i++)
        scanf("%d",&list[i]);
    
    for(int i=1;i<=W;i++){
        int startIndex = 0,lastIndex=0;
        for(int j=1;j<i;j++)
            if(list[j]>list[startIndex])
                startIndex = j;
        for(int j=i+1;j<=W;j++)
            if(list[j]>list[lastIndex])
                lastIndex = j;
        
        if(list[startIndex]>list[i] && list[lastIndex]>list[i])
            sum += (min(list[startIndex],list[lastIndex])-list[i]);
    }
    printf("%d",sum);
}