백준 14719 빗물

문제링크 : https://www.acmicpc.net/problem/14719

아이디어

• 전체에서 빗물이 어떻게 담기는지 계산하는건 어려움
  • 이런 히스토그램에서는 x축에서 한칸한칸 계산해주는 것이 쉬움
  • 빗물이 담기는 기준 : 왼쪽에서 가장 큰값과 오른쪽에서 가장큰값 중 더 작은값까지 채워짐
  • 왼쪽과 오른쪽에서 최대값을 각각 구함
  • 각 x 칸에서, 왼쪽과 오른쪽값 중 더 작은값과, 현재 값을 비교해서 현재값이 더 작으면 그 차이만큼 더함

시간복잡도 계산

• 왼쪽, 오른쪽 모두 최대값 구하기 : O(W)
  • 모든x축에 대해서 : O(W)
  • 차이구하기
  • 총합 : O(W + W) : O(W) > 가능

자료구조

• int maxLeft[510] : 왼쪽중 최대값
  • 최대값 500이므로 INT 가능
    • int maxRight[510] : 오른쪽 중 최대값
  • 최대값 500이므로 INT 가능
    • int map[510] : 각 칸에서의 높이
    • 총합 : int cnt
  • 최대값 : 500*500 = 250000 > INT 가능

코드(C++)

#include <iostream>
 
using namespace std;
 
int map[510];
int maxLeft[510];
int maxRight[510];
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int H,W; cin >> H >> W;
    int maxv = 0;
    for(int i=0; i<W; i++) {
        // 값 기록하면서 왼쪽부터 최대값 등록하기
        cin >> map[i];
        maxv = max(maxv, map[i]);
        maxLeft[i] = maxv;
    }
    
    // 오른쪽에서부터 최대값 구하기
    maxv = 0;
    for(int i=W-1; i>=0; i--) {
        maxv = max(maxv, map[i]);
        maxRight[i] = maxv;
    }
    
    int cnt=0;
//    모든 위치순회
    for(int i=0; i<W; i++) {
        int minv = min(maxLeft[i], maxRight[i]);
        if(minv > map[i]) cnt += minv - map[i];
    }
    
    cout << cnt << '\n';
    return 0;
}
 

문제유형

• 시뮬레이션 - 히스토그램
  • 이런 히스토그램 문제 나올떄, 일정 구간 * 높일를 구하면 어려워짐
  • 각각 위치에서 값을 더해주면 쉽게 할수있음

비슷한 문제

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