[백준 1911번 / C++] 흙길 보수하기

[백준 2170번 / C++] 선 긋기

---

위의 문제와 유사하니 풀어보길 권한다. 

 

투포인터를 활용한 문제이다.

 

1. pair 구조를 가진 벡터를 오름차순으로 정렬. 

2. 첫번째 벡터 쌍의 시작위치값을 start에 저장하고 end 라는 변수에는 시작위치값 + 물웅덩이 길이를 저장. 

3. 벡터 사이즈만큼 반복문을 돌린다.

 

이때, 벡터 쌍의 원소 중 시작 위치 값이 start 변수의 값보다 크다면 이전 웅덩이에서 활용했던 널빤지가 현재 웅덩이에 영향을 주지 않는다는 뜻이다. 즉, 새로운 웅덩이 시작위치가 널빤지의 시작위치이며 그렇기 때문에 위의 2번과 같이 start와 end변수에 값을 저장해준다.  

이후 벡터 쌍의 원소 중 끝 위치 값이 start 변수의 값보다 클 동안, 널빤지의 개수를 하나씩 추가해주면서 start와 end의 값을 갱신해나간다. 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	ios::sync_with_stdio(0); 
	cin.tie(0);  
	int n, l; 
	cin >> n >> l; 
	vector <pair <int, int>>v; 
	for (int i = 0; i < n; i++) {
		int a, b; cin >> a >> b; 
		v.push_back({ a,b });
	}
	sort(v.begin(), v.end()); 
	int s, e; 
	s = v[0].first; 
	e = v[0].first+l;
	int cnt = 0; 
	for (int i = 0; i < v.size(); i++) {
		if (s < v[i].first) {
			s = v[i].first; 
			e = v[i].first + l; 
		}
		while (s < v[i].second) {
			cnt++;
			s = e;
			e = s + l;
		}		
	}
	cout << cnt; 
}

 

1911번: 흙길 보수하기