BOJ 1449 수리공 항승

BOJ 1449 수리공 항승

문제링크 : https://www.acmicpc.net/problem/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";
}