[백준 알고리즘/C++/그리디] 1449 수리공 항승

 

 

파이프에 구멍 난 곳을 수리하는 항승이..

구멍 난 곳 좌우로 0.5만큼 테이프를 붙이는데, 테이프는 중간에 자를 수 없고 겹쳐서 붙일 수 있다

수리를 위해 써야 하는 테이프의 최소 개수를 구하는 문제

 

 

좌우로 0.5만큼 붙이니까 그냥 1이라 생각하자

 

3 4 5 에 구멍이 났고, 테이프의 길이 L=5라면 테이프 하나로 모두 수리할 수 있다

3 10 12 에 구멍이 났고, 테이프의 길이는 마찬가지고 5라면 테이프가 2개 필요하다

3 부분에 하나, 10 12 부분에 하나를 붙여주면 된다

 

구멍이 처음 난 곳을 start, 테이프 길이 안에 포함된 가장 끝 지점을 end라고 했을 때

start ~ end 사이의 구멍들은 모두 테이프 하나로 수리할 수 있다

L=5, 3 4 7 8 에 구멍이 났을 때 start=3, end=8 이라며 테이프 하나 쓴다고 하면 안됨

정확히는 2.5~7.5 부분을 테이프로 붙이는거니까.. 8은 다시 start가 되어야 함

 

for문으로 start와 end를 계속 바꿔주면 된다

end - start >= L 이면 테이프를 count 해준다

그리고 end가 start가 되어 계산을 이어나가면 된다

 

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int n, l;
    int arr[1001];
 
    cin >> n >> l;
    for(int i=0;i<n;i++) {
        cin >> arr[i];
    }
 
    sort(arr, arr + n);
 
    int res = 1, start = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] - start >= l) {
            res++;
            start = arr[i];
        }
    }
 
    cout << res;
}

 

하... 예제는 입력값 정렬되어 있길래 정렬된 값 주는 줄 알고 sort 안했다가 틀렸고,

변수 l을 실수로 i라 적었는데 잘 안보여서 한참 찾았다