글 읽기 - 소소한 반례 하나 던져놓고 갑니다. (정답 소스코드 포함)

psmdc0714 2년 전 5

입력

1 5

2 4

3 2

4 3

5 1

출력

스택으로 문제를 푸는 경우에 내림차순으로 이루어지는 기둥들에서 지붕이 오목해지는 경우를 제대로 처리하지 않은 경우라고 볼 수 있습니다.

저는 8%에서 계속 틀리고 나머지 테스트 케이스들은 모두 통과하길래 의아했었는데, 스택에 지금까지 있던 가장 높은 기둥보다 더 높은 기둥이 나오는 경우만 생각했지 스택 안에 있는 가장 높은 기둥보단 낮지만 스택의 top에 있는 기둥보다 큰 경우를 제대로 걸러내지 못했었네요.

소스코드 또한 공유합니다. 스택에 기둥이 오름차순/내림차순으로만 존재할 수 있게끔 구상하였습니다.

제 수준이 고수는 아니라 이런 식으로 풀 수도 있구나 정도로 생각하면 될 거 같아요.

28-30줄이 없을 경우 오답으로 15를 출력하게 됩니다.

#include <bits/stdc++.h>
using namespace std;
#define L first
#define H second
int n, res;
pair<int, int> a[1000];
stack<pair<int, int>> s;
int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for(int i=0; i<n; i++){
        int l, h;
        cin >> l >> h;
        a[i] = {l, h};
    }
    // 무작위로 들어오는 경우를 감안하여 L 오름차순 순서로 정렬함
    sort(a, a+n);
    
    int maxH = 0; // 스택 안의 제일 높은 기둥 높이 저장용 변수
    for(int i=0; i<n; i++){
        if(!s.empty() && a[i].H > s.top().H) // top의 기둥보다 높을 경우
            if(a[i].H > maxH) // 스택 안의 가장 높은 기둥보다 높을 경우
                while(s.top().H != maxH) // 해당 기둥이 나올 때까지 pop
                    s.pop();
            else // 스택 안의 가장 높은 기둥보단 낮을 경우
                while(s.top().H < a[i].H) // 내림차순이 만들어질 때까지 pop
                    s.pop();
        maxH = max(maxH, a[i].H); // 스택 내 기둥 최대 높이 갱신
        s.push(a[i]);
    }

    while(!s.empty()){
        auto cur = s.top();
        s.pop();
        res += cur.H; // 현재 기둥이 차지하는 넓이룰 더해줌
        if(s.empty()) continue;
        // top의 기둥과 현재 기둥 사이의 여분 면적을 계산함
        if(cur.H < s.top().H)
            res += (cur.L - (s.top().L + 1)) * cur.H;
        else
            res += (cur.L - (s.top().L + 1)) * s.top().H;
    }
    cout << res;

    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

소소한 반례 하나 던져놓고 갑니다. (정답 소스코드 포함)

psmdc0714 2년 전 5

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말