백준 2283: 구간 자르기

 

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

 

이 문제는 풀이법이 재미있어서 다뤄보려한다.

해결을 위해서 누적 합과 투 포인터란 다소 생소한 조합을 사용해야하는 것이 흥미로웠다.

 

큰 그림은 다음과 같다.

왼쪽 끝 점과 오른쪽 끝 점을 두고, 그 사이의 선분의 길이가 K보다 작으면 오른쪽 끝점을 오른쪽으로 옮기면서 해당 위치에 있는 선분의 길이를 더하고, K보다 크다면 왼쪽 끝점을 오른쪽 옮기면서 이전 위치에 있던 선분의 길이를 뺀다.

기본적인 투 포인터 사용법이다. 여기서 해당 위치의 "선분의 길이"는 해당 위치의 "선분의 갯수"와 같다고 봐도 무방하다.

 

그렇다면 여기서 특정 위치의 선분의 갯수는 어떻게 구해야할까?

N = 1,000이고, 양 끝점 위치의 최대가 1,000,000인 만큼 단순하게 Bruteforce를 사용하면 시간초과가 난다.

 

누적합을 사용해볼까? 만약 선분의 길이가 1, 500이면 1에서 500까지 반복문을 돌며 배열에 +1을 하는 방식이다.

근데 이것도 Bruteforce와 큰 차이가 없어 보인다.

이렇게 생각할즈음에 내가 이전에 비슷한 고민을 한 적이 있다는 것을 깨달았다.

https://sumserv.tistory.com/105

백준 17611: 직각다각형

정확히는 

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

이 문제다.

 

간단히 말하면, 처음과 끝에 +와 -를 두고, 누적합을 통해 답을 구할 수 있다는 것이다.

예를 들어서 선분 1 5, 4 7 이 있다고 하자.

그럼 배열 값을

0 1 0 0 1 -1 0 -1 0 0

다음과 같이 둘수 있다. 여기서 처음부터 합을 누적시키면서, 해당 위치의 합을 배열로 만들면 다음과 같다.

0 1 1 1 2 1 1 0 1 1

이렇게 하면 각 위치의 선분의 갯수를 구할 수 있다.

 

그렇게 만들어진 코드는 다음과 같다.

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX = 1000001;
int N, K, E[MAX], A, B, ans1 = 0, ans2 = 0, L[MAX], s = 0;

int main()
{
	ios_base::sync_with_stdio(false);
	cout.tie(NULL); cin.tie(NULL);
	cin >> N >> K;
	for (int i = 0; i < N; i++)
	{
		cin >> A >> B;
		E[A]++;
		E[B]--;
	}
	for (int i = 0; i < MAX; i++)
	{
		s += E[i];
		L[i] = s;
	}
	int l = 0, r = 1; s = L[0];
	while (r < MAX)
	{
		if (s == K)
		{
			ans1 = l;
			ans2 = r;
			break;
		}
		else if (s > K)
		{
			while (l < r && s > K)
			{
				s -= L[l];
				++l;
			}
		}
		else
		{
			while (r < MAX && s < K)
			{
				s += L[r];
				++r;
			}
		}
	}
	cout << ans1 << " " << ans2 << '\n';
}

예전에 해결한 문제를 기억하고, 이렇게 재밌있는 문제를 풀 수 있는 열쇠가 되어서 간만에 뿌듯했다.