[백준 2283] 구간 자르기

문제 링크: https://www.acmicpc.net/problem/2283

2283번: 구간 자르기

<문제 풀이> 투포인터, 누적합 알고리즘

 

먼저 모든 구간을 살펴봐야 하고 각 구간에 존재하는 막대기의 총길이가 K가 되도록 하는 조건이 있기 때문에 이 문제는 투포인터와 누적합을 사용해서 해결할 수 있습니다.

 

원래 모든 구간을 살펴보기 위해선 O(구간의길이^2)의 시간복잡도가 걸리지만, 각 구간에 존재하는 막대기의 총길이가 K가 되도록 하는 조건은 투포인터 문제로 변환할 수 있어서 O(구간의 길이)의 시간복잡도만 걸리게 됩니다.

 

1. 구간에 존재하는 막대기의 총 길이를 O(1)에 구하기 위해서 누적합을 사용합니다.

먼저 막대기를 표현하는 방법을 생각해봐야 하는데 입력으로 주어진 막대기의 왼쪽 좌표, 오른쪽 좌표 그리고 1차원 배열을 이용하면 막대기를 쉽게 표현할 수 있습니다.

 

예를 들어

[0, 3]인 막대기 한 개를 표현하면 아래와 같습니다.

bar[0] = 1, bar[3] = - 1

 

[0, 3]인 막대기를 0부터 3까지 순회하면서 현재 좌표의 배열값과 이전 배열의 값을 누적하면 각 좌표에 존재하는 막대기의 개수를 구할 수 있습니다.

idx 0 1 2 3 

val 1 1 1 0

 

마찬가지로,  [0, 3] 인 막대기, [0, 8]인 막대기 두 개를 표현하면 아래와 같습니다.

bar[0] = 2, bar[3] = -1, bar[8] = -1;

 

누적합을 구하면

idx 0 1 2 3 4 5 6 7 8 

val 2 2 2 1 1 1 1 1 0

 

즉 입력으로 주어진 막대기의 좌표를 가지고 bar[left]++, bar[right]--을 하면 막대기를 표현할 수 있습니다.  또한 배열을 순회하면서 누적합을 구하면 각 좌표에 해당하는 막대기의 개수를 구할 수 있습니다.

 

추가적으로 bar[i]는 [i - 1, i] 구간에 존재하는 막대기의 총길이와 같습니다.

 

2. 누적합을 가지고 투포인터로 모든 구간을 살펴보면서 구간의 길이의 총합이 K가 되는 구간을 구한다.

 

이제 투포인터 기본 문제랑 똑같습니다. left =0, right =0부터 시작하면서 구간을 점점 키워나가면 되는데, 이때 right를 증가시켰는데 K를 넘어가면 더 이상 right를 증가시킬 필요가 없습니다. 왜냐하면 누적합이기 때문에 right를 더 증가시켜 봤자 K가 되는 답을 구할 수 없으므로 이때 left를 증가시키면 됩니다. 따라서 이 문제는 투포인터로 해결할 수 있습니다.

 

 

 

<C++소스코드>

 

 

#include<iostream>
using namespace std;

int bar[1000001]; //bar[i] : [i - 1, i] 구간에 존재하는 막대기의 총길이
int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int n, k; cin >> n >> k;

	for (int i = 0; i < n; i++) { 
		int a, b; cin >> a >> b;
		bar[a]++; //막대기 시작점과 끝점 표현 -> [a, b]
		bar[b]--; 
	}
	for (int i = 1; i <= 1000000; i++) {
		bar[i] += bar[i - 1]; // [i-1, i] 구간에 존재하는 막대기의 총길이 계산
	}


	int right = 0;
	int sum = bar[0];
	for (int left = 0; left <= 1000000; left++) { // 현재 바라보는 구간 : [left, right]
		while (right + 1 < 1000000 && sum < k) { //막대기의 길이가 아직 k가 안 된 경우 
			right++;
			sum += bar[right]; // 늘어난 구간만큼(right) 막대기 총길이 누적
		}
		if (sum == k) { // k가 되는 구간을 찾으면 출력 후 종료
			cout << left << ' ' << right + 1 << '\n';
			return 0;
		}
		sum -= bar[left]; // 더이상 right를 증가시켜도 만족하는 구간이 없으므로 left를 증가시키면서 구간을 감소, 줄어든 구간만큼(left) 막대기 총길이 감소
	}
	cout << 0 << ' ' << 0; //k가 되는 구간이 존재하지 않는 경우


	return 0;
}