[BOJ] 1911번: 흙길 보수하기

문제 링크

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

접근한 방식

그리디 알고리즘으로 해결하였다.
앞에서 차례대로 웅덩이의 빈틈이 없게 널빤지를 덮어나가기만 하면 된다. 그런데 널빤지가 다음 웅덩이의 일부분 또는 전부를 덮을 수도 있을 것이다. 이럴때는 다음과 같이 처리한다.

• 다음 웅덩이를 이전 널빤지가 전부 덮어버렸을 경우
  • 그냥 다음 과정으로 넘어간다.
• 다음 웅덩이를 이전 널빤지가 일부 덮어버렸을 경우
  • 이전 널빤지가 덮은 제일 끝 위치의 다음 위치를 시작으로 하여 널빤지를 덮어나간다.

코드

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, L;
vector<pair<int, int>> poolLocation;
int index;
int result;

int main(void) {
	scanf("%d %d", &N, &L);

	poolLocation.resize(N);

	for (int i = 0; i < N; i++) 
		scanf("%d %d", &poolLocation[i].first, &poolLocation[i].second);
	
	sort(poolLocation.begin(), poolLocation.end());

	for (int i = 0; i < N; i++) {
		int beginLocation = poolLocation[i].first;
		int endLocation = poolLocation[i].second;

		if (index >= endLocation - 1) continue;

		if (index >= beginLocation)
			beginLocation = index + 1;
		else
			index = beginLocation - 1;

		int scope = endLocation - beginLocation;

		if (scope % L == 0 && scope != 0) {
			int pools = scope / L;
			
			for (int j = 0; j < pools; j++) 
				index += L;
			
			result += pools;
		}
		else {
			int pools = scope / L + 1;
			
			for (int j = 0; j < pools; j++)
				index += L;

			result += pools;
		}
	}

	printf("%d\n", result);

	return 0;
}