[백준/c++] BOJ 1449 - 수리공 항승

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

1449번: 수리공 항승

 

문제 설명

물이 새는 파이프를 수리하려고 한다.

파이프의 가장 왼쪽에서 정수만큼 떨어진 거리에서만 물이 샌다.

길이가 L인 테이프를 무한개 가지고 있고, 물을 막을 때 그 위치의 좌우 0.5만큼 간격을 줘서 막으려고 한다.

테이프를 자를 수 없고, 겹쳐서 붙이는 것은 가능할 때, 수리에 필요한 테이프의 최소 개수를 구한다.

물이 새는 곳 N (1 <= N <= 1000), L (1 <= L <= 1000)

해결

테이프를 최소한으로 사용해야 하므로, 테이프 하나로 여러개의 구멍을 막는 것이 중요하다.

따라서 가까이 있는 물이 새는 곳은 테이프 하나로 처리하도록 해야 한다. 물이 새는 곳을 받아 정렬하고, 인접해 있는 구멍들이 길이 L의 테이프로 막아지면 테이프 하나로 막아 주었다.

 

구멍들의 간격과 테이프의 길이를 비교할 때 구멍의 간격에 1을 더해 주어 좌우 0.5 간격 조건까지 신경 써 주면 된다.

 

코드

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;

int n, m;
int ans = 1;
vector<int> v;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		v.push_back(a);
	}
	
	sort(v.begin(), v.end());
	int j = 0;

	for (int i = 1; i < n; i++) {
		if (v[i] - v[j] + 1 <= m)
			continue;
		else {
			ans++;
			j = i;
		}
	}
	cout << ans;
}