알고리즘
백준 1911번 흙길 보수하기 C++
영춘권의달인
2023. 2. 8. 12:08
https://www.acmicpc.net/problem/1911
1911번: 흙길 보수하기
어젯밤 겨울 캠프 장소에서 월드 본원까지 이어지는, 흙으로 된 비밀길 위에 폭우가 내려서 N (1 <= N <= 10,000) 개의 물웅덩이가 생겼다. 월드학원은 물웅덩이를 덮을 수 있는 길이 L (L은 양의 정수)
www.acmicpc.net
우선 웅덩이를 오름차순으로 정렬하고
지금까지 설치한 널빤지의 위치가 웅덩이의 시작지점보다 앞에 있으면 웅덩이의 시작지점부터 다시 설치하고
웅덩아의 시작지점이거나 뒤에 있으면 뒤에 이어서 설치한다.
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>
using namespace std;
using int64 = long long;
int n, l;
vector<pair<int, int>> v;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> l;
v = vector<pair<int, int>>(n);
for (int i = 0; i < n; i++) {
int s, e;
cin >> s >> e;
v[i] = { s,e };
}
sort(v.begin(), v.end());
int curr = 0;
int ans = 0;
for (int i = 0; i < n; i++) {
if (curr < v[i].first) curr = v[i].first;
while (curr < v[i].second) {
curr += l;
ans++;
}
}
cout << ans;
}