1911_흙길 보수하기

▶실버1

 

풀이

1. 주어진 웅덩이를 정렬한다.

2. 한 웅덩이에 대해 몫과 나머지를 구한 후 몫의 개수만큼 널빤지를 사용한다.

2-1. 나머지가 존재하면 널빤지를 하나 더 더해준다.

2-2. 나머지가 존재하지 않으면 건너뛴다.

3. 현재 위치가 웅덩이가 아니라면 다음 웅덩이의 첫 위치를 현재 위치로 설정한다.

 

코드

#include <iostream>
#include <ctime>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;

vector <pair<int, int>> pool;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int ans = 0;
	int n, l;
	cin >> n >> l;
	for (int i = 0; i < n; i++) {
		int start, end;
		cin >> start >> end;
		pool.push_back({ start, end });
	}

	sort(pool.begin(), pool.end());
	int cur = pool[0].first;
	for (int i = 0; i < n; i++) {
		if (cur < pool[i].first) { cur = pool[i--].first; }

		else if (pool[i].first <= cur && cur < pool[i].second) {
			int sub = pool[i].second - cur;
			ans += sub / l;
			cur += (sub / l) * l;

			if (sub % l != 0) {
				ans++;
				cur += l;
			}
		}
	}
	cout << ans;
}