[BOJ/C++] 1863 스카이라인 쉬운거

문제

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

풀이

스카이라인

y좌표가 감소할 때만 건물 개수 카운트해주고, 최종적으로 스택에 남아있는 수를 카운트해주면 됨 (0 제외)


아래 그림과 같은 논리임

코드

#include <iostream>
#include <stack>

using namespace std;

stack<pair<int, int>> s;
int ans = 0;

void sol(int x, int y) {
	if (s.empty())	s.push({ x, y });
	else {
		if (s.top().second < y)	s.push({ x, y });
		else {
			while (!s.empty() && s.top().second > y) {
				s.pop();
				ans++;
			}
			if (!s.empty() && s.top().second != y)	s.push({ x,y });
			if (s.empty())	s.push({ x, y });
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		int x, y;
		cin >> x >> y;
		sol(x, y);
	}

	while (!s.empty()) {
		if (s.top().second != 0) ans++;
		s.pop();
	}

	cout << ans;

	return 0;
}