[개쉬운 풀이] 백준 1863 스카이라인 쉬운거

 

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

문제

도시에서 태양이 질 때에 보이는 건물들의 윤곽을 스카이라인이라고 한다. 스카이라인만을 보고서 도시에 세워진 건물이 몇 채인지 알아 낼 수 있을까? 건물은 모두 직사각형 모양으로 밋밋하게 생겼다고 가정한다.

정확히 건물이 몇 개 있는지 알아내는 것은 대부분의 경우에 불가능하고, 건물이 최소한 몇 채 인지 알아내는 것은 가능해 보인다. 이를 알아내는 프로그램을 작성해 보자.

생각

1. 현재 입력으로 스카이라인의 고도가 '바뀌는' 지점의 좌표를 제시하고 있다.
2. 그렇다면 고도가 바뀌기 전까지는 같은 건물로 취급하면된다.
3. 이를 테트리스처럼 생각하여서 풀었다.
4. 현재 고도보다 낮은 고도가 입력으로 들어오면 원래 건물은 하나의 건물로 취급하고 삭제한다.
5. 같은 고도가 나올 경우 이전 건물과 같은 건물의 고도일 수 있다.
6. 현재 고도보다 높은 고도가 나온다면 다음 고도를 스택에 추가하여 저장한다.

풀이

input()

1. 입력값을 저장한다.

sol()

1. stack = 건물의 고도 저장
2. stack에 0을 넣어 초기값을 저장한다.
3. for문을 활용하여 다음 고도의 변화에 따라 프로세싱한다.

process()

1. 스택의 최상단(back)과 현재 빌딩의 고도(빌딩)를 비교한다.
2. 백 < 빌딩인 경우 빌딩의 고도를 추가한다.
3. 같은 경우 현재 스택에 같은 고도가 있으므로 다음으로 넘어간다. (테트리스와 같이 같은 건물 취급)
4. 백 > 빌딩인 경우 백의 빌딩은 더이상 같은 그림자를 공유하는 경우가 없으므로 pop을 한 다음 answer을 1 증가시킨다.
5. 이어서 다음건물 탐색이 아닌 현재의 건물과 스택의 최상단을 다시 비교한다.
6. 왜냐하면 현재 건물을 저장할지, 넘길지 아직 결정한 것이 아니기 때문.

#include <iostream>
#include <vector>
using namespace std;

struct T{
    int x, y;
};

int n;
vector<T> v;
vector<int> stack;
int answer = 0;

//입력
void input(){
    cin >> n;
    for(int i = 0; i < n; i++){
        T tmp;
        cin >> tmp.x >> tmp.y;
        v.push_back(tmp);
    }
}

void process(int building, int back){
	//더 큰 건물의 그림자는 저장
    if(back < building && building != 0){
        stack.push_back(building);
    }
    //스택의 고도와 빌딩의 고도가 같으면 같은 건물 취급
    else if(back == building){
        return;
    }
    //스택의 최상단은 하나의 건물로 더이상 같은 고도가 나올 수 없다.
	//따라서 pop을 해주고 정답 + 1
    else{
        stack.pop_back();
        answer++;
        process(building, stack.back());
    }
}

void sol(){
	//초기값 세팅 
    //0만 들어오는 것을 방지
    stack.push_back(0);
    for(int i = 0; i < n; i++){
        int building = v[i].y;
        //스택이 비면 추가한다.
        if(stack.empty()){
            stack.push_back(building);
            continue;
        }
        int back = stack.back();
        process(building, back);
    }

    cout << answer + stack.size()-1<< endl;
  
}

int main(){
    input();
    sol();
    return 0;
}