수리공 항승 C++ - 백준 1449

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

그리디 문제.

문제 접근

테이프를 붙일 때에 최대한 테이프의 손실이 없게 하면서,

최대한 많이 붙여야한다.

그리고 위치에 따라 순차적으로 붙여야 하기 때문에,

arr를 정렬해주고 알고리즘을 수행해야 한다.

처음 원소부터 다음 원소 위치-처음 원소 위치 + 1이 테이프 길이보다

큰 지 확인해 나가면서 이미 붙인 인덱스는 bool에서 판단해주었다.

코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

void solve(){
	int n,l;
	int ans=0;
	cin >> n >> l;
	vector<int> arr(n);
	vector<bool> f(n);
	fill(f.begin(),f.end(),false);
	for(int i=0;i<n;i++) cin >> arr[i];
	sort(arr.begin(),arr.end());
	int s=arr[0]; int e=arr[0];
	int ck=0;
	for(int i=0;i<n;i++){
		if(!f[i]){
			while(e-s+1<=l && ck<n){e=arr[++ck];f[ck]=true;}
			if(ck==n){
				if(e-s+1>l){ans++;continue;}
			}
			f[ck]=false; s=e=arr[ck]; ans++;
		}		
	}
	cout << ans;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	solve();
}