[BOJ 1449] 수리공 항승(C++)

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

1449번: 수리공 항승

 

 

물이 새는 곳을 다 막을 수 있는 테이프의 최소 개수를 알아봐야 한다.

 

 

 

구멍난 곳부터 시작해서 막는 것이 더 많은 범위를 커버할 수 있다. (그리디 알고리즘)

 

 

 

해설코드(C++).

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int N, L;
int val, answer = 0;
vector<int> v;
 
int main() {
    cin >> N >> L;
    for(int i = 1; i <= N; i++){
        cin >> val;
        v.push_back(val);
    }
    
    sort(v.begin(), v.end());
    L -= 1;
    if(v.size() > 0){
        int start = v[0] + L;
        answer += 1;
        
        for(int i = 1; i < v.size(); i++){
            if(start < v[i]){ 
                start = (v[i] + L);
                answer += 1;
            }
        }
    }
    
    cout << answer << endl;
    return 0;
}