[백준 1449번] 수리공 항승 (C++)

문제링크 : https://www.acmicpc.net/problem/1449

1449번: 수리공 항승

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int L, N,arr[1001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N >> L;
    for(int i=0; i<N; i++) cin >> arr[i];
    sort(arr, arr+N); //정렬

    int cnt = 1;
    int start = arr[0];
    for(int i=1; i<N; i++)
    {
        if(arr[i] - start < L) continue; //테이프가 충분하면 스킵
        start = arr[i]; //테이프 시작점 갱신
        cnt++; //테이프 갯수 증가
    }

    cout << cnt;
    
    return 0;
}

 

어렵지 않은 정렬문제이지만, 테이프 사용시 좌우 간격 0.5씩 사용한다는 점에 주의하여야 한다.

따라서 다른 위치 - 시작점의 값이 총 테이프 길이보다 작아야만 테이브를 붙일 수 있다.

 

테이프 길이가 같아지는 순간부터는 시작점에서 이미 테이프를 사용해서 모자란 상태이다.

이때부터는 해당 위치가 테이프 시작점으로 갱신되며, 필요 테이프 갯수가 증가하게 된다.