[BOJ] 1449번 수리공 항승

풀이

하나의 테이프를 갖고 최대한 넓은 범위를 커버하는 것이 목표인 문제였습니다.
그러기 위해서 먼저 물이 새는 곳의 위치가 저장된 배열을 정렬해 주었습니다.
이후 반복문을 이용하여 테이프로 최대 몇개의 구멍까지 메울 수 있는지를 확인했습니다.
주의해야 할 점은 구멍을 막을 때, 적어도 그 위치의 좌우 0.5만큼 간격을 줘야한다는 점입니다. 이를 적용하려면 두 구멍 사이의 거리를 구할 때 추가적으로 1을 더해주어야 우리가 원하는 조건을 만족시킬 수 있습니다.
if (list[i] - st + 1 > tape) 조건식을 이용하여 하나의 테이프로 최대한 많은 구멍을 메울 수 있게끔 해주었습니다.

코드

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

void init() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
}

int main() {
	init();

	int list[1001];
	int ans = 1;
	int n, tape;

	cin >> n >> tape;

	for (int i = 0; i < n; i++)
		cin >> list[i];

	sort(list, list + n);
	int st = list[0];

	for (int i = 1; i < n; i++)
	{
		if (list[i] - st + 1 > tape)
		{
			ans++;
			st = list[i];
		}

	}

	cout << ans;

	return 0;
}

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