백준 1863 - 스카인라인 쉬운거

문제 설명

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

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 빌딩의 높이가 변경될 때 x, y좌표가 x의 오름차순으로 주어질때, 최소한의 빌딩의 개수를 구하는 것이다.

문제를 글로만 읽으면 이해하기 어려울 수 있다.

예시를 봐보자.

10
1 1
2 2
5 1
6 3
8 1
11 0
15 2
17 3
20 2
22 1

위의 예시를 색으로 건물을 분류한 것이다.

 

문제의 핵심은 어느 건물이 앞인지 뒤인지 알 수 없는 상황에서 건물을 분류하기 위해서는 건물의 시작과 끝을 알아내는 것이다.

다른 말로하면, 이 건물이 진짜 이어진 건지는 모르지만 확실히 끊기는 부분은 찾아낼 수 있다는 것이다.

확실히 끊기는 부분은 해당 건물의 시작 높이보다 더 작은 높이를 만난다면 해당 건물은 이어져있을 수 없다.

예를 들어, (2, 2)에서 시작한 건물은 (5, 1)에 나온 건물과 같은 건물일 수 없다는 것이다.

 

그렇다면, 건물의 높이가 변하는 부분을 알고있기 때문에 해당 부분에서 더 낮은 건물로 변하지 않는다면 해당 건물은 이어져있다고 생각할 수 있다.

또한, 높이가 같은 건물은 다시 체크하면 안되기 때문에 방문 체크를 통해 중복을 제거한다.

마지막으로, 높이가 0에서 시작하는 부분이 있을 수 있다.

해당 부분은 위에서 말한 논리가 적용되지만 건물 수는 올리지 않게 해주어야 한다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <list>
#include <bitset>

using namespace std;

int N;


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    vector<pair<int, int>> skyline;
    for (int i = 0; i < N; i++)
    {
        int x, y;
        cin >> x >> y;
        skyline.push_back({ x,y });
    }

    int ans = 0;
    vector<bool> visited(N, false);
    for (int i = 0; i < N; i++)
    {
        if (visited[i]) continue;
        for (int j = i+1; j < N; j++)
        {
            if (skyline[i].second > skyline[j].second) break;
            if (skyline[i].second == skyline[j].second) visited[j] = true;
        }

        if(skyline[i].second != 0) ans++;
    }

    cout << ans;
    return 0;
}

---