[BOJ] 1449번 : 수리공 항승

매우 간단한 greedy와 sort 문제이다.

 

입력받은 물이 새는 위치를 정렬하고, 정렬된 값을 앞에서부터 테이프를 가장 많이 남기는 방식으로 붙여나가면 된다. 이것의 정당성 증명은 간단하다. 특정 물이 새는 위치 leak[i]까지만 보았을 때, leak[i]가 이미 테이프로 cover되어 있다면 테이프를 붙이지 않는 것이 자원을 가장 아끼는 방법이고, 테이프가 cover되어 있지 않다면 테이프를 가장 많이 남기는 방식으로, 즉 leak[i]-0.5 지점부터 붙이는 것이 가장 자원을 아끼는 방법이다. leak[i]까지만 보았을 때는 이보다 효율적인 방법은 없고, leak[n]까지 이를 반복하면 된다.

 

시간복잡도는 NlogN + N = O(NlogN)이다.

 

#include <stdio.h>
#include <algorithm>
 
using namespace std;
 
const int maxN = 1050;
int n, l;
int leak[maxN];
 
int main ( void ) {
    
    int recent = -1;
    int cnt = 0;
    
    scanf("%d %d", &n, &l);
    for (int i = 0; i < n; i++) scanf("%d", &leak[i]);
    
    sort(leak,leak+n);
    
    
    for(int i = 0; i < n; i++) {
        if(leak[i] <= recent) continue;
        
        recent = leak[i]+ l - 1;
        cnt++;
    }
    printf("%d\n", cnt);
}