[백준][C++] 1449: 수리공 항승

문제

1449번: 수리공 항승

풀이

그리디, 정렬

 

구멍이 정렬되어 들어오지 않으므로 정렬이 필수이다. 

// 정렬 필수
sort(hole.begin(), hole.end());

 

구멍 start에서 테이프를 붙였을 때, 막을 수 있는 구멍의 거리는 start + L - 1까지이다. 이 거리보다 먼 구멍은 막을 수 없으므로, 새로운 테이프를 사용해야 한다. start + L - 1에서 다음 구멍 까지는 테이프를 붙이지 않아도 되므로, 다음 구멍이 start가 되어 다시 start + L - 1까지 테이프가 붙여진다. 

// 현재 구멍 i에서 테이프를 붙였을 때, 막을 수 있는 구멍의 거리는 hole[i] + L - 1 까지이다.
// 이 거리보다 먼 구멍은 막을 수 없으므로, 새로운 테이프를 사용해야 한다. 
int answer = 0;
int start = hole[0];
for (int i = 0; i < N; ++i)
{
    if (hole[i] > start + L - 1)
    {
        // start를 갱신한다.
        start = hole[i];
        answer++;
    }
}

// 마지막 start에서 사용하는 테이프
cout << answer + 1;

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> hole;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, L;
    cin >> N >> L;

    for (int i = 0; i < N; ++i)
    {
        int temp;
        cin >> temp;
        hole.push_back(temp);
    }

    // 정렬 필수
    sort(hole.begin(), hole.end());

    // 현재 구멍 i에서 테이프를 붙였을 때, 막을 수 있는 구멍의 거리는 hole[i] + L - 1 까지이다.
    // 이 거리보다 먼 구멍은 막을 수 없으므로, 새로운 테이프를 사용해야 한다. 
    int answer = 0;
    int start = hole[0];
    for (int i = 0; i < N; ++i)
    {
        if (hole[i] > start + L - 1)
        {
            // start를 갱신한다.
            start = hole[i];
            answer++;
        }
    }

    // 마지막 start에서 사용하는 테이프
    cout << answer + 1;

    return 0;
}