[백준 2283] 구간 자르기 (C++)

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

2283번: 구간 자르기

 

문제

---

수직선(數直線) 상에 구간 N개가 있다. 임의의 두 정수 A, B(A < B)를 정하여, 각 구간에서 A와 B 사이에 포함되지 않은 부분을 모두 잘라냈을 때 남는 부분들의 길이의 총합이 K가 되도록 하여라.

 

입력

---

1번째 줄에 정수 N, K(1 ≤ N ≤ 1,000, 1 ≤ K ≤ 1,000,000,000)가 주어진다.

2~N+1번째 줄에 각 구간의 왼쪽 끝점과 오른쪽 끝점의 위치가 주어진다. 양 끝점의 위치는 0 이상 1,000,000 이하의 정수이다.

 

출력

---

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

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

 

문제 풀이

---

투포인터 문제.

0부터 1,000,000까지의 누적합을 구해 sums 배열에 저장한 후 (i에 저장되어 있는 값은 0부터 i까지의 길이의 합이 된다. ), 두 포인터 start와 end를 0의 위치에 둔다.

start부터 end까지의 사이의 구간의 합은 start가 0이라면 처음부터 끝까지의 범위를 구하는 것이므로 sums[end]가 된다.

만약 start가 0이 아니라면 처음부터 끝까지의 범위에서 처음부터 start까지의 범위를 빼면 되므로 sums[end]-sums[start]가 된다.

구간의 합이 구하려는 K보다 작다면 end를 1 증가시켜 구간의 합을 키워보고, K보다 작다면 start를 1 증가시켜 구간의 합을 줄여본다. 만약 K라면 start가 A이고, end가 B인 답이 된다. 조건을 만족하는 A, B가 여러개 있더라도 start와 end를 0부터 찾아나갔으므로 이 범위가 A와 B가 가장 작은 경우가 된다.

범위의 마지막인 1,000,000까지 end를 증가시켰는데도 찾지 못했다면 조건을 만족하는 A, B가 없는 것이므로 0 0을 출력해주면 된다.

 

아래는 코드.

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

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

	int N, K;
	cin >> N >> K;

	int sum = 0;
	int s, e;
	int* arr = new int[1000001];
	int* sums = new int[1000001];
	for (int i = 0; i < 1000001; i++)
	{
		arr[i] = 0;
		sums[i] = 0;
	}
	for (int i = 0; i < N; i++)
	{
		cin >> s >> e;
		for (int j = s+1; j <= e; j++)
		{
			arr[j]++;
		}
	}
	sums[0] = 0;
	for (int i = 1; i < 1000001; i++)
	{
		sums[i] = sums[i - 1] + arr[i];
	}
	int start = 0;
	int end = 0;
	int A = 0;
	int B = 0;
	while (end <= 1000000)
	{
		if (start == 0)
		{
			sum = sums[end];
		}
		else
		{
			sum = sums[end] - sums[start];
		}
		if (sum < K)
		{
			end++;
		}
		else if (sum == K)
		{
			A = start;
			B = end;
			break;
		}
		else
		{
			start++;
		}
	}
	std::cout << A <<" " << B << "\n";
	return 0;
}