boj, 백준) 1911. 흙길 보수하기(C/C++)

1. 문제 링크

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

1911번: 흙길 보수하기

 

2. 문제 개요

흙으로 된 비밀길 위에 폭우가 내려서 N[1,10000] 개의 물웅덩이가 생겼다. 물 웅덩이를 덮을 수 있는 길이 L(양의 정수) 짜리 널빤지등을 충분히 가지고 있어서 물웅덩이를 모두 덮으려고 한다.

 

물 웅덩이들의 위치와 크기에 대한 정보가 주어질 때, 모든 물웅덩이들을 덮기 위해 필요한 널빤지들의 최소 개수를 구하라.

 

3. 문제 힌트

극단적으로 이런 경우를 생각해보자. 웅덩이가 [10,13] [14,16], [17,19]에 있고 널빤지의 길이가 10이라고 가정했을 때,

널빤지는 [10,19]에 놓음으로써 1개 만에 해결할 수 있다.

그런데, [5,14] [15,24] 이렇게 놓아서 2개로도 해결할 수 있다.

 

웅덩이를 만났을 때, 어떻게 하면 가장 최선으로 놓을 수 있을까? 

Greedy 하게..  주어진 상황에서 어떻게 놓아야 최소화할 수 있을지 생각해보자.

 

 

4. 문제 풀이

가장 먼저 해야 할 것이 웅덩이의 시작점을 기준으로 정렬하는 것이다.

왜냐하면 왼쪽에서 오른쪽으로 한번 훑고 지나갈 건데, 이때 웅덩이의 위치가 정렬되어 있어야 3. 문제 힌트에서 있었던 경우를 처리해줄 수 있기 때문이다.

 

아이디어는 정말 간단하다.

웅덩이를 덮을 때 시작점에 딱 맞춰서 널빤지를 붙이면 최적이다. 여기서 최적이라는 것은 널빤지의 개수를 최소화할 수 있다.

너무 자명해서 증명이라고 할 게 없다.

 

정렬된 상태에서 널빤지를 시작점(왼쪽)에 딱 맞춰서 붙여나간다라고 생각하고 문제를 풀어보자.

 

널빤지가 다른 웅덩이를 일부 덮는다면 거기서부터 계속 붙여나가고,

그렇지 않고 널빤지의 끝이 일반 땅이라고 하면 그다음 웅덩이의 왼쪽에서부터 다시 붙여나가면 된다.

 

5. 코드

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

int n, l;
vector<pair<int, int>> v;

int main()
{
	scanf("%d %d", &n, &l);
	v.resize(n);

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

	int cur = 0;
	int ans = 0;

	for (int i = 0; i < n; ++i) {
		if (v[i].first <= cur && cur < v[i].second) {
			int quotient = (v[i].second - cur) / l;
			int remainder = (v[i].second - cur) % l;
			
			ans += quotient;
			cur += quotient * l;

			if (remainder != 0) {
				++ans;
				cur += l;
			}
			
		}
		else if( cur < v[i].first)
		{
			cur = v[i].first;
			--i;
		}
		else if (v[i].second <= cur)
		{
			//nothing to do
		}
	}

	
	printf("%d", ans);

	return 0;
}

 

6. 결과