백준 알고리즘 1449번 - 수리공 항승

그리디 알고리즘을 사용하는 문제.

간단히 생각해보면, 앞에 부터 채워나간다고 생각하면 편하다.

이미 채워져있다면 넘어가고, 채워지지 않았다면 채우는 과정을 반복한다.

 

// 1. 오름차순 정렬
// 2. 맨 왼쪽꺼 0.5 떨어진 지점에 테이프를 붙임 +1
// 3. 다음 지점 앞뒤로 + 0.5지점에 테이프가 붙어있다면
// 3-1 . 3번이 true라면 다음 지점으로 건너 뛰고 3번으로
// 3-2 . 3번이 false라면 2번으로 간다.
#include <iostream>
#include <algorithm>

using namespace std;

//0.5처리하기 싫으니까 다 두배로 하자.
int arr[4000]={0};
bool check[4000]={false};

int main()
{
	int n,l,count=0;
	cin>>n>>l;
	l=l*2;
	
	for(int i=0;i<n;i++){
		cin>>arr[i];
		arr[i]=arr[i]*2;
	}
	sort(arr,arr+n);
	for(int i=0;i<n;i++){
		if(check[arr[i]]){
			//cout<<"already taped : "<<arr[i]<<endl;
			continue;
		}
		else{
			for(int j=0;j<l-1;j++)
			{
				check[arr[i]+j]=true;
				//cout<<"막는다"<<arr[i]+j<<endl;
			}
			count++;
		}
	}
	cout<<count;
}