BOJ 1449 수리공 항승

문제 링크 : https://www.acmicpc.net/problem/1449

1449번: 수리공 항승

요약

물이 새는 곳의 위치와, 항승이가 가지고 있는 테이프의 길이 L이 주어졌을 때, 항승이가 필요한 테이프의 최소 개수를 구하는 문제(구멍을 막으려면 좌우 0.5 간격이 필요함, 테이프는 겹쳐도 됨)

풀이

구멍을 막을때 좌우 0.5 간격이 필요함으로 1이 필요하다. 테이프로 한 번에 간격의 길이가 L-1인 구간을 덮을 수 있다. 제일 왼쪽에 있는 점부터 시작하여 오른쪽으로 길이 L-1인 구간을 다 덮고, 그 오른쪽부터 다시 점을 찾아 덮는 걸 반복하면 된다.

코드

#include<iostream>
#include<algorithm>
using namespace std;
int N, L, arr[1001];
int main() {
	cin >> N >> L;
	for (int i = 0; i < N; i++)
		cin >> arr[i];
	sort(arr, arr + N);
	int start = 0;
	int ans = 1;
	for (int i = 0; i < N; i++) {
		if (arr[i] > arr[start] + (L - 1)) {
			start = i;
			ans++;
		}
	}
	cout << ans << "\n";
}