[알고리즘] 백준1911 흙길 보수하기

문제

백준1911 흙길 보수하기

---

구상

• 해결해야 할 것
  • 웅덩이의 범위가 겹치는 경우 처리
  • 웅덩이의 범위와 널빤지의 길이에 따른 처리

웅덩이의 범위가 겹치는 경우 처리

위치에 해당하는 배열을 만들어 웅덩이를 저장할까?

위치값은 최대 10억이므로 10억짜리 배열을 만들 수 없다!
-> 라인스위핑을 이용하자.

웅덩이의 범위와 널빤지 길이의 관계

웅덩이의 크기가 널빤지의 길이로 나누어 떨어지지 않을 경우, 처리를 해주어야 한다.

---

코드

#include<bits/stdc++.h>
using namespace std;
int n,l,s,e,endPoint,ret;
vector<pair<int,int>> v;
int main(){
	cin>>n>>l;
	for(int i=0; i<n; i++){
		cin>>s>>e;
		v.push_back({s,e});
	}
	sort(v.begin(),v.end());
	for(int i=0; i<v.size(); i++){
		if(v[i].second < endPoint) continue; // case1 : 완전히 겹침 
		// case2 : 일부분이 겹침 
		else if (v[i].second >= endPoint && v[i].first < endPoint){
			int num = v[i].second - endPoint;
			ret += (num)/l + (num%l ? 1 : 0);
			endPoint += l*((num/l) + (num%l ? 1 : 0));
		}
		else{ // case3 : 겹치지 않음 
			int num = v[i].second - v[i].first;
			ret += num/l + (num%l ? 1 : 0);
			endPoint =v[i].first + l*((num/l)+ (num%l ? 1 : 0));
		}
	}
	cout<<ret;
	return 0;
}

시작점을 기준으로 정렬된 벡터를 돌며 다음과 같이 처리한다.

• case1 : 웅덩이가 완전히 겹치는 경우 : continue
• case2 : 웅덩이의 일부분이 겹치는 경우 : endPoint를 기준으로 널빤지를 추가하고 endPoint를 갱신한다.
• case3 : 겹치지 않는 경우 : 웅덩이의 시작점을 기준으로 널빤지를 추가하고 endPoint를 갱신한다.