취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1911번 문제인 흙길 보수하기이다.
문제는 아래 링크를 확인하자.

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

수직선 위에 각 물웅덩이를 [L,R)과 같이 나타내고(문제 하단의 힌트그림 참고), 널빤지의 길이를 X라 하자. 이 때 L값이 가장 작은 웅덩이서부터 각 물웅덩이를 널빤지를 놓아 덮어나가는 것으로 문제를 해결할 수 있다. 각 널빤지를 새로 놓을 때, 널빤지의 왼쪽 좌표가 아직 안 덮인 물웅덩이의 가장 왼쪽과 일치하게 놓아나가자.

널빤지를 하나하나 놓아가며 웅덩이를 덮는 알고리즘은 것은 비효율적이므로, 각 (정렬된 순서의) 웅덩이 별로 지금까지 덮인 범위와 웅덩이의 길이를 이용해 식을 세워 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, X;
pair<int, int> pit[10000];
int ans;

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

	cin >> N >> X;
	for (int i = 0; i < N; i++) cin >> pit[i].first >> pit[i].second;

	sort(pit, pit + N);
	int covered = -1;
	for (int i = 0; i < N; i++) {
		int L = pit[i].first, R = pit[i].second;
		R--;
		if (covered >= R) continue;
		if (covered < L) covered = L - 1;
		int tmp = (R - covered - 1) / X + 1;
		ans += tmp;
		covered += tmp * X;
	}

	cout << ans;
}