백준 2304 창고 다각형

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

아이디어

• 오목하게 들어간 부분이 없으니까, 최대값까지 점점 증가해야함
• 최대값을 기준으로 왼쪽에서는 계속 증가해야하고, 오른쪽에서는 계속 감소해야함
• 맨 오른쪽부터 시작해서 최대값까지 점점 증가하면 됨

시간복잡도 계산

• 최대값 인덱스 구하기 : O(N)
• 왼쪽에서부터, 오른쪽에서부터 최대값까지 순회 : O(N)

자료구조

• 기둥 높이 기록 : map[N]
  • 최대값 : 1000 > INT 가능
    • 왼쪽에서부터 최대값 int maxLeft
  • 최대값 : 1000 > INT 가능
    • 오른쪽에서부터 최대값 int maxRight
  • 최대값 : 1000 > INT 가능
    • 모두 더한값 rs
  • 1000 * 1000 > 1e6 > INT 가능

코드(C++)

#include <iostream>
 
using namespace std;
 
int map[1010];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N; cin >> N;
    int maxv = 0;
    int maxi = 0;
    // 값 받으면서 최대값 인덱스 찾자
    for(int i=0; i<N; i++) {
        int a,b; cin >> a >> b;
        map[a] = b;
        if(map[a] > maxv ) {
            maxi = a;
            maxv = map[a];
        }
    }
    
    int rs=0;
    
    // 왼쪽에서부터 최대값 더함
    int maxLeft = 0;
    for(int i=0; i<maxi; i++) {
        maxLeft = max(maxLeft, map[i]);
        rs += maxLeft;
    }
    
    // 오른쪽쪽에서부터 최대값 더함
    int maxRight = 0;
    for(int i=1000; i>=maxi; i--) {
        maxRight = max(maxRight, map[i]);
        rs += maxRight;
    }
    
    cout << rs << '\n';
    return 0;
}
 

문제유형

• 시뮬레이션 - 히스토그램
  • 히스토그램 문제는 전체를 한번에 구하려면 어려워짐
  • 각각 위치에서 값을 더해주면 쉽게 할수있음

비슷한 문제

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