[백준/BOJ] 백준 2283번 : 구간 자르기

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

2283번: 구간 자르기

 

구간의 왼쪽 끝점에 +1, 구간의 오른쪽 끝점에 -1을 표시하여 이를 누적합을 수행하여, 구간을 나타내었고, 이를 기반으로 투 포인터를 이용해, 투 포인터의 범위의 합이 k가 되는 경우를 확인하는 방법으로 문제를 해결했다.

 

코드

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

int n, k;
int check[1000005];
int psum[1000005];
int max_right = 0;

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

	cin >> n >> k;

	for (int i = 0; i < n; i++) {
		int l, r;
		cin >> l >> r;

		check[l] += 1;
		check[r] -= 1;

		max_right = max(max_right, r);
	}

	for (int i = 0; i <= 1000000; i++) {
		if (i == 0) {
			psum[i] = check[i];
			continue;;
		}

		psum[i] = psum[i - 1] + check[i];
	}

	int left = 0;
	int right = 0;
	int sum = 0;
	while (1) {

		if (right > max_right) {
			left = 0;
			right = 0;
			break;
		}

		if (sum < k) { //right를 오른쪽으로
			sum += psum[right];
			right++;
		}

		else if (sum > k) { //left를 오른쪽으로
			sum -= psum[left];
			left++;
		}

		else { //부분 길이의 총합이 k가 될대
			break;
		}
	}

	cout << left << " " << right << "\n";

	return 0;
}