수리공 항승 (백준 - 1449번)

그리디 알고리즘을 사용하는 문제였다.

 

우선 물이 새는 곳의 위치를 입력받으면 그 정보를 정렬한다. 그 다음 처음 물이 새는 곳의 위치를 기록한다.(start값)    

 

물이 새는 곳이 하나라도 있으면 테이프를 한 개는 써야 하므로 테이프의 갯수를 기록할때는 1부터 시작한다.

 

테이프를 최소로 쓰기 위해서 어떻게 해야 하는지 살펴보자. 물이 새는 위치를 순회하며 start에서 물이 새는 위치까지의 길이가 테이프의 길이 - 1(좌우 0.5만큼 간격을 줘야 하므로) 보다 큰 경우 이미 테이프의 길이를 넘어 갔으므로 start부분만 막고 새로운 테이프로 현재 위치를 막아야 한다. 그리고 start값을 현재 위치의 값으로 갱신한다. 모든 위치를 방문했을때 테이프의 갯수가 우리가 원하는 값이 된다.

 

코드는 다음과 같다.

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

int main()
{
	vector<int> leakPos;

	int leakCount;
	int tapeLength;
	cin >> leakCount >> tapeLength;
	leakPos.resize(leakCount);

	for (int i = 0; i < leakCount; ++i)
	{
		cin >> leakPos[i];
	}

	sort(leakPos.begin(), leakPos.end());

	int tapeCount = 1;
	int start = leakPos[0];
	for (int i = 1; i < leakCount; ++i)
	{
		if (tapeLength - 1 < leakPos[i] - start)
		{
			++tapeCount;
			start = leakPos[i];
		}
	}

	cout << tapeCount << endl;
}