[백준/BOJ/알고리즘/파이썬(python)/C++/그리디/정렬]#1449_수리공 항승

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

1449번: 수리공 항승

그리디 알고리즘과 정렬 알고리즘

정렬은 파이썬과 c++ 모두 STL 라이브러리로 한줄로 쉽게 끝난다.

정렬을 함으로써 그리디 알고리즘을 쉽게 구현할 수 있습니다. 

 

파이썬 코드

#1449
N, L = map(int, input().split())
leak = list(map(int, input().split()))
leak.sort()
start = leak[0]
end = leak[0]+L
tape = 1

for i in range(N):
    if start<= leak[i] < end:
        continue
    if end > 1000:
        continue
    else:
        start = leak[i]
        end = leak[i]+ L
        tape += 1

print(tape)

c++코드

#include<iostream>
#include<algorithm>
using namespace std;
const int MAX=1000+1;
int main(){
	int N, L;
	cin>>N>>L;
	int leak[1000]={0,};
	for(int i=0;i<N;i++)
		cin>>leak[i];
		
	sort(leak, leak+N);
	
	int start = leak[0];
	int end = leak[0]+L;
	int tape =1;
	
	for(int i=0;i<N;i++){
		if(start<=leak[i]&&leak[i]<end)
			continue;
		if(end>1000)
			continue;
		else{
			start = leak[i];
			end = leak[i]+L;
			tape++;
		}
	}
	
	cout<<tape;
		
}