[BOJ-2283] 구간 자르기(C++)

백준 2283 줄세우기

 

2283번: 구간 자르기

 

문제 설명

 

 - 수직선 상 구간 N개가 있다.

 

 - 임의의 두 정수 A, B(A<B)를 정하여, 각 구간에서 A와 B 사이에 포함되지 않은 부분을

   모두 잘라냈을 때 남는 부분들의 길이의 총합이 K가 되도록 하여라.

 

 

 - 두 정수 A, B를 출력한다. 조건을 만족하는 A, B가 존재하지 않으면 "0 0"을 출력한다.

   조건을 만족하는 A, B가 여러 개 존재할 때는 A가 가장 작은 경우를 출력한다.

   그것도 여러 개 존재할 때는 B가 가장 작은 경우를 출력한다.

---

 

 

입력 값

 

 - 1번째 줄에 정수 N, K 가 주어진다.

    ( 1 <= N <= 1,000 / 1 <= K <= 1,000,000,000 )

 

 - 2-N+1 번째 줄에 각 구간의 왼쪽 끝점과 오른쪽 끝점의 위치가 주어진다.

   양 끝점의 위치는 0이상 1,000,000 이하의 정수이다.

 

---

 

 

예제

---

 

문제 분석

 

 - 이 문제를 간단하게 정의하면, 구간 사이의 수직선의 길이의 합이 K인 구간을 찾는 방법이다.

 

 - 두 구간 사이를 살펴보는 문제이기 때문에 투포인터를 이용하면 간단하게 풀 수 있다.

투 포인터, 슬라이딩 윈도우 기법

 

 - 문제 풀이 과정은 다음과 같다.

   1. 두 범위 start와 last가 0부터 시작한다.

   2. start와 last 사이의 수직선의 길이의 합(SUM)과 K를 비교한다.

   3. SUM > K 인 경우 수직선을 줄여야 하기 때문에 start++를 하고 SUM을 구한 후 2번으로 돌아간다.

   4. SUM < K 인 경우 수직선을 늘려야 하기 때문에 last++를 하고  SUM을 구한 후 2번으로 돌아간다.

   5. SUM == K 인 경우 정답이 되기 때문에 종료한다

  

 - start++가 일어났을 때 SUM을 구하는 방법은 다음과 같다.

   0. start가 지나간 범위의 수직선의 종료 값을 우선순위큐에 넣는다.

   1. start++가 일어났다면, 해당 값보다 작은 값을 우선순위큐에서 제거한다.

   2. 우선순위큐에 남아 있는 값은 start++가 일어나면서 줄어든 값이기 때문에

      그 값 만큼 SUM에서 제거한다.

   3. start++ 후 그 값을 시작으로 하는 수직선을 우선순위 큐에 넣는다.

 

 - last++가 일어났을 때 SUM을 구하는 방법은 다음과 같다.

   0. last가 지나간 범위의 수직선의 종료 값을 우선순위큐에 넣는다.

   1. last++가 일어났다면, 해당 값보다 작은 값을 우선순위큐에서 제거한다.

   2. 우선순위큐에 남아 있는 값은 last++가 일어나면서 늘어난 값이기 때문에

      그 값 만큼 SUM에서 더해준다.

   3. last++ 후 그 값을 시작으로 하는 수직선을 우선순위 큐에 넣는다.

 

 

 - 주의할 점은 범위를 찾을 수 없는 경우 0 0을 리턴해야 한다는 점이다.

 

---

 

 

소스 코드

#include <bits/stdc++.h>

using namespace std;


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

	int N, K;
	int sum = 0;
	cin >> N >> K;

	vector<pair<int, int>> node;

	for (int i = 0; i < N; i++) {
		int a, b;
		cin >> a >> b;
		node.push_back({ a,b });
	}

	sort(node.begin(), node.end());

	int start = 0;
	int last = 0;

	int startIndex = 0;
	int lastIndex =0 ;

	priority_queue<int,vector<int>,greater<int>> startPQ;
	priority_queue<int,vector<int>,greater<int>> lastPQ;

	for (int i = 0; i < node.size(); i++) {
		if (node[i].first == 0) {
			startPQ.push(node[i].second);
			lastPQ.push(node[i].second);
			startIndex = i+1;
			lastIndex = i + 1;
		}
		else {
			break;
		}
	}

	sum = 0;

	while (last <= 1000000) {

		if (sum > K) {
			start++;
			while (!startPQ.empty()) {
				if (startPQ.top() < start) {
					startPQ.pop();
				}
				else {
					break;
				}
			}
			
			sum -= startPQ.size();

			for ( startIndex; startIndex < node.size(); startIndex++) {

				if (node[startIndex].first <= start) {
					startPQ.push(node[startIndex].second);
				}
				else {
					break;
				}

			}


		}
		else if (sum == K) {
			break;
		}
		else {
			last++;
			while (!lastPQ.empty()) {
				if (lastPQ.top() < last) {
					lastPQ.pop();
				}
				else {
					break;
				}
			}
			sum += lastPQ.size();
			for (lastIndex; lastIndex < node.size(); lastIndex++) {

				if (node[lastIndex].first <= last) {
					lastPQ.push(node[lastIndex].second);
				}
				else {
					break;
				}

			}

			
		}
	}

	if (last == 1000001) {
		last = 0;
	}

	cout << start << " " << last << endl;

	return 0;
}