백준 1449. 수리공 항승

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

1449번: 수리공 항승

 

 

1. 물이 세는곳의 위치를 오름차순 정렬한다.

2. 반복문을 돌면서 첫위치부터 테이프를 붙인다.

3. 이전에 붙인 테이프의 끝위치를 기억해서 (물세는위치-0.5+L) 다음 물세는 위치가 이전 테이프의 끝위치보다 작으면 

    이전 테이프로 커버되므로 스킵한다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n,l;
vector<int> pipe;

int main()
{
    cin >> n >> l;
    for(int i = 0; i < n; i++)
    {
        int num;
        cin >> num;
        pipe.push_back(num);
    }

    // 오름차순 정렬
    sort(pipe.begin(), pipe.end());

    int cnt = 0;
    double end = 0;
    for(int i = 0; i < n; i++)
    {
        // 이전에 붙인 테이프가 현재 물이 세는곳 위치를 커버하면 continue
        if(end > pipe[i]) continue;
        end = pipe[i]-0.5+l;

        cnt++;
    }
    cout << cnt;
}