[BOJ] 14719번 : 빗물(C++)

김영한·2021년 4월 6일
0

알고리즘

목록 보기
37/74

문제 링크 : 백준 14719번

[문제 접근]

  1. left, right를 현재 인덱스의 값으로 초기화한다.(현재 인덱스의 값이 왼쪽, 오른쪽의 최대값보다 클 경우를 방지)
  2. 현재 인덱스를 기준으로 왼쪽의 최대값, 오른쪽의 최대값을 구한다.
  3. 왼쪽값과 오른쪽값 중에 최소값을 구한다.
  4. 최소값에서 현재 인덱스의 값을 뺀걸 ans에 더한다.
  5. 첫 번째와 마지막 인덱스는 비교대상이 없으므로 할 필요없다.

[소스 코드]

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;
int h, w;
int arr[501];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> h >> w;
    for(int i=0 ; i<w ; i++) {
        cin >> arr[i];
    }
    int ans=0;
    for(int i=1 ; i<w-1 ; i++) {
        int left = arr[i], right = arr[i];
        for(int j=0 ; j<i ; j++) {
            left = max(left, arr[j]);
        }
        for(int j=i+1 ; j<w ; j++) {
            right = max(right, arr[j]);
        }
        int now = min(left, right);
        ans += now-arr[i];
    }
    cout << ans << "\n";
}

0개의 댓글