[알고리즘] C++ 백준 2283 구간 자르기

백준 2283

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

2283번: 구간 자르기

풀이 전 나의 생각

수직선 상에 구간 N개와 두 정수 A, B (A < B) 가 주어질 때,

A와 B에 포함 되어있는 구간의 합이 K가 되도록 하는 A와 B의 값을 구해야 한다.

 

조건

- 1 ≤ N ≤ 1,000, 1 ≤ K ≤ 1,000,000,000

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

 

과정

(0, 0)부터 (0, 1000000)의 범위를 N번의 최대인 1000번 탐색한다고 가정했을 때,

1000000 * 1000 = 10억의 계산 횟수가 나오기 때문에 브루트포스 같은 개념으로
접근하면 안된다.

 

따라서 누적합 + 투 포인터를 이용하면 굉장히 빠른속도로 문제를 풀어나갈 수 있다.(O(logN))

 

과정은 다음과 같다.

1. 초기에 주어지는 구간의 시작 위치 0 부터 끝 위치 까지 누적합을 구해준다. 

2. 시작과 끝 포인터를 0으로 설정한다.

3. 누적합 배열을 0부터 끝 포인터로 탐색하며 최종값이 K가 될 때 까지 더해준다.

4. 최종값이 K보다 커졌다면 누적합 배열의 시작 포인터 값을 빼주며 증가시켜준다. 

5. K와 최종값이 같아졌다면 시작과 끝 포인터를 출력한다.

 

예를 들어 현재 누적합 배열이 (1, 1, 2, 3, 4), K 는 5일 때

end 포인터0 -> 3 까지 갔다면 1 + 1 + 2 + 3으로 K값을 초과해버린다.

따라서 start 포인터를 증가시켜주며 기존에 있던 값을 빼준다.

start 포인터 0 -> 1 == 1 + 1 + 2 + 3 -> 1 + 2 + 3 (K == 5)

따라서 최종값이 같아졌기 때문에 시작과 끝 포인터를 출력해준다. (1, 3)

 

좀 더 설명하자면 누적합 배열이 (1, 3, 5, 7, 4)이라면
0을 지나는 구간은 1개
1을 지나는 구간은 3개
2를 지나는 구간은 5개
3을 지나는 구간은 7개
4를 지나는 구간은 4개 라는 의미다.

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>
#include <map>

using namespace std;

int ver[1000001];

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

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

	for (int i = 0; i < N; i++)
	{
		int start, end;
		cin >> start >> end;
		
		for (int j = start + 1; j <= end; j++)
		{
			//구간의 누적합을 구해준다.
			ver[j]++;
		}
	}

	int start = 0, end = 0, ans = 0;

	// end만 계속해서 높아질 수 있기 때문에 주의해야 한다.
	while (start <= end && end <= 1000000)
	{
		//최종값이 K와 같아졌다면 결과 출력
		if (ans == K)
		{
			cout << start << " " << end;
			return 0;
		}
		//최종값이 K보다 작다면 끝 포인터 증가
		else if (ans < K) 
		{
			ans += ver[++end];
		} 
		//최종값이 K보다 크다면 시작 포인터 증가
		else 
		{
			ans -= ver[++start];
		}
	}
	// 결과 출력에 실패했다면 0 0 출력
	cout << "0" << " " << "0";
}