[1449] 수리공 항승

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

1449번: 수리공 항승

<문제>

우선, 입력을 받고 정렬해준다.

어떤 물이 새는 곳이 아직 막혀있지 않다면, 그 위치의 -0.5부터 시작하는 길이 l의 테이프를 붙여줄 것이다.

0.5라는 수치가 다소 애매한데, 어처피 입력은 정수이므로

a[i]를 막기 위해서 테이프를 붙이면, [a[i], a[i]+l-1]의 위치는 전부 테이프로 막히게 된다.

이후로는 테이프로 어디까지 막혀있는지를 저장하는 변수(cur)만 하나 사용하여, 테이프를 붙여나가면 되겠다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, l;
int main(void) {
    int i, j;
    cin >> n >> l;
    vector<int> a(n);
    for (i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());
    int cur = 0, answer = 0;
    for (i = 0; i < n; i++) {
        if (a[i] > cur) {
            cur = a[i] + l - 1;
            answer++;
        }
    }
    cout << answer;
    return 0;
}