1449 수리공 항승

1449. 수리공 항승 / c++ / Silver3 / 10분

문제

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

1. 첫 째줄에 파손된 파이프 위치의 수 N과, 항승이 가지고 있는 테이프의 길이 L이 주어진다.
2. 파이프를 수리하려면 파손된 위치의 좌우 0.5만큼 간격윽 줘야한다.
3. 항승이가 모든 파이프를 수리하는데 필요한 테이프의 최소 갯수는?

접근 방식

그리디, 우선순위 큐

1. 라인 스위핑으로 가장 먼 위치부터 고치기로 한다. (맥스힙인 우선순위 큐를 그대로 사용하기 위함)
2. 커버 가능한 범위는
   현재 파손된 위치 - 테이프의 길이 + 0.5(좌우 0.5만큼의 간격이 있어야하므로 파손된 위치보다 0.5 더 멀리 붙여야한다)
3. 현재 테이프가 붙어있는 위치에서 커버가 가능하려면
   다음 파손된 위치 - 0.5 가 현재 테이프가 붙여진 위치보다 멀어야한다.
   다시말해 다음 파손된 위치 < 현재 테이프가 붙여진 최소 위치 + 0.5 이면 테이프를 새로 붙여야한다.
4. 2번과 3번을 priority_queue가 빌 때까지 실행한다.

문제 풀이

#pragma GCC optimize("Ofast")
#include <iostream>
#include <queue>

using namespace std;

priority_queue<int> pq;

int N, L, num, answer = 0;
float now;

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    
    cin >> N >> L;
    
    for (int i = 0; i < N; ++i)
    {
        cin >> num;
        pq.push(num);
    }
    
    answer++;
    now = pq.top() - L + 0.5f; pq.pop();
    
    while (!pq.empty())
    {
        if ((float)pq.top() < now + 0.5f)
        {
            answer++;
            now = pq.top() - L + 0.5f;
        }
        pq.pop();
    }
    
    cout << answer << '\n';
    
    return 0;
}

다시 생각해 볼 점

1. using namespace std를 안써서 컴파일 에러가 났다. 실수하지 말자
2. 그것 외에는 한번에 풀었다. 이번엔 정렬된 값이 필요했으므로 우선순위 큐를 활용했다.
3. 이처럼 특정 값을 기준으로 정렬하여 순회하면서 푸는 라인스위핑이 그리디 알고리즘과 맞물릴 수도 있다.
   그럴때는 우선순위 큐가 딱인 것 같다. (역시 우선순위 큐는 그리디와 잘 맞는다.)