1449-空港リフト-グリディアルゴリズムの修理

質問する

ポリシー

コード#コード#

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

int N, L;

int main(){

    // freopen("../input.txt","rt",stdin);
    
    scanf("%d %d",&N, &L);
    int tmp;
    vector<int> hole;
    for(int i=0; i<N; i++){
        scanf("%d",&tmp);
        hole.push_back(tmp);
    }
    // 홀을 크기에 따라 정렬하는 것은 중요하다.
    sort(hole.begin(), hole.end());
	
    // tape를 가장 첫번째 위치한 hole-1의 테이프의 길이를 더해준 것으로 한다.
    // hole을 하나 채우는데 1의 길이가 필요하므로 hole[0]-1을 해준것이고, 
    //테이프를 하나 사용해야하므로 L을 더해주었다.
    int tape = hole[0]-1 + L;
    
    int cnt = 1;
    for(int i=1; i<hole.size(); i++){
    	// hole의 위치가 tape의 위치보다 크면 새로운 tape의 위치를 할당해주고 cnt++을 해준다.
        if(hole[i] > tape){
            tape = hole[i] - 1 + L;
            cnt++;
        }
    }
    printf("%d\n",cnt);
    return 0;
}

感想