[G5] 백준 2170번 선 긋기 C++ 우선순위 큐, 스위핑

리뷰

 

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

일 직선상으로 선을 긋고, 그려진 선(들)의 총 길이를 구하는 문제

우선순위 큐 혹은 정렬을 통해 구현할 수 있는 아주 간단한 문제이다.

 

전역 변수

• n : 선을 그은 횟수를 입력 받을 정수형 변수
• x, y : 그은 선의 시작점 x와 도착점 y를 표시하기 위한 정수형 변수
• Line : 각 선의 정보를 저장하기 위한 구조체, 우선 순위 큐 활용을 위해 내부에 cmp함수를 작성한다.

 

함수

없음

 

 

문제풀이

1. 구조체 Line타입의 우선순위 큐 pq를 초기화 해준다.
2. n값을 입력 받고, n개의 선의 정보를 입력 받아 pq에 push해준다.
3. 끝 선의 위치를 저장할 변수 l을 -10억으로 초기화 해주고, 선의 길이를 저장할 변수 len을 0으로 초기화 한다.
4. n개의 선을 순회하며 만약 현재 선의 x가 l보다 클 경우 l을 현재 선의 시작점으로 맞추어 준다.
5. 현재 선의 y가 l보다 클 경우 그 차이만큼 len을 더해주고 l을 현재 선의 y로 맞추어 준다.
6. 모든 탐색이 끝난 후 len에 저장되어 있는 값을 출력해 준다.

 

참고 사항

구조체로 정의하지 않고 pair<int, int>로 해도 된다.

큐에 선 정보를 모두 넣었으니 pq가 빌때까지 반복문을 실행해도 된다.

 

 

정답 코드

#include<iostream>
#include<queue>

using namespace std;

int n, x, y;

struct Line {
	int x, y;
	bool operator<(const Line& other) const {
		if (x == other.x) return y < other.y;
		return x > other.x;
	}
};

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

	priority_queue<Line> pq;

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x >> y;
		pq.push({ x, y });
	}

	int l = -1000000000;
	int len = 0;
	for (int i = 0; i < n; i++) {
		Line line = pq.top(); pq.pop();
		if (l < line.x) l = line.x;

		if (l < line.y) {
			len += line.y - l;
			l = line.y;
		}
	}
	cout << len;
}