백준 1449번: 수리공 항승

[문제 링크]

1449번: 수리공 항승

---

간단한 그리디 알고리즘 문제였다.

물이 새는 곳의 위치를 내림차순 정렬한 다음, 물이 새는 곳의 거리가 테이프의 길이보다 짧은지 긴지 비교한다.

 

물이 새는 곳의 거리가 테이프의 길이보다 짧다면 다음 장소까지 매꿀 수 있는지 비교해보고,

길다면 테이프 하나로 매꿀 수 없으므로 사용한 테이프를 1 증가시키고 다음 장소와 비교한다.

---

#include <iostream>
using namespace std;

void Quick_sort(int data[], int start, int end)
{
	if (start >= end) return;

	int pivot = start;
	int i = start + 1;
	int j = end;

	while (i <= j)
	{
		while (i <= end && data[i] > data[pivot])
			i++;
		while (j > start && data[j] < data[pivot])
			j--;

		if (i > j)
		{
			int temp = data[pivot];
			data[pivot] = data[j];
			data[j] = temp;
		}
		else
		{
			int temp = data[i];
			data[i] = data[j];
			data[j] = temp;
		}
	}

	Quick_sort(data, start, j - 1);
	Quick_sort(data, j + 1, end);
}

int Greedy(int arr[], int N, int L)
{
	Quick_sort(arr, 0, N - 1);

	int cnt = 0, tape = L - 1;
	
	for (int i = 1; i < N; i++)
	{
		int dist = arr[i - 1] - arr[i];
		if (dist > tape)
		{
			tape = L - 1;
			cnt++;
		}
		else
			tape -= dist;
	}

	return cnt + 1;
}

int main(void)
{
	int N, L, arr[1000];
	cin >> N >> L;

	for (int i = 0; i < N; i++)
		cin >> arr[i];

	cout << Greedy(arr, N, L) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 119 day