[C++] 백준 온라인 저지 1449번 수리공 항승 풀이

물이 새는 수도관을 수리하는 데 필요한 테이프의 최소 갯수를 구하는 문제

 

---

문제의 조건

 

항승이는 품질이 심각하게 나쁜 수도 파이프 회사의 수리공이다. 항승이는 세준 지하철 공사에서 물이 샌다는 소식을 듣고 수리를 하러 갔다.

파이프에서 물이 새는 곳은 신기하게도 가장 왼쪽에서 정수만큼 떨어진 거리만 물이 샌다.

항승이는 길이가 L인 테이프를 무한개 가지고 있다.

항승이는 테이프를 이용해서 물을 막으려고 한다. 항승이는 항상 물을 막을 때, 적어도 그 위치의 좌우 0.5만큼 간격을 줘야 물이 다시는 안 샌다고 생각한다.

물이 새는 곳의 위치와, 항승이가 가지고 있는 테이프의 길이 L이 주어졌을 때, 항승이가 필요한 테이프의 최소 개수를 구하는 프로그램을 작성하시오. 테이프를 자를 수 없고, 테이프를 겹쳐서 붙이는 것도 가능하다.

 

입력

첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 항승이가 필요한 테이프의 개수를 출력한다.

 

 

풀이 과정

 

 항승이가 테이프를 붙일 때 양 옆으로 최소 0.5미터 간격을 준다고 했으니까 1 ~ 2 미터에 테이프를 붙인다면 0.5 ~ 2.5 거리에 테이프를 붙이게 됩니다. 그러면 1 ~ 2 간 떨어진 간격은 1이지만 양 옆 여유 간격 0.5 들을 더하면 최소 2미터의 테이프가 있어야 1 ~ 2 거리에 테이프를 붙일 수 있습니다. 

 그렇기 때문에 주어지는 테이프의 길이 L - 1 만큼 연속해 있는 위치들은 테이프 하나로 막을 수 있습니다. 입력으로 주어지는 위치들을 우선순위 큐를 사용해서 내림차순으로 정렬한 다음 L - 1 만큼 연속해 있는 위치 덩어리들의 갯수를 세서 정답으로 출력했습니다. 

 

1. 물이 새는 위치를 저장할 우선순위 큐를 만든다. 내림차순으로 정렬할 것이기 때문에 최대힙으로 만든다. 

 

2. 첫번째 위치와 큐의 다음 순서에 있는 위치들의 거리가 L - 1 보다 작으면 테이프 하나로 붙일 수 있으니까 넘어가고 L - 1 보다 크면 테이프로 한 번에 붙일 수 없으니까 테이프의 갯수를 하나 증가시킨다. 테이프의 갯수를 증가시키고 나면 현재 위치는 끊긴 지점으로 바꾼다. 큐가 빌 때까지 반복한 후 테이프 갯수 출력 

 

 

코드

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main()
{
    int N, L;
    cin >> N >> L;
    
    priority_queue<int> leakSpots; //내림차순 정렬 최대힙 
    for (int i = 0; N > i; i++)
    {
        int a;
        cin >> a;
        leakSpots.emplace(a);
    }
    
    //맨 뒤에서부터 시작 
    int curSpot = leakSpots.top();
    leakSpots.pop();
    int answer = 0;
    while (!leakSpots.empty())
    {
        //테이프 하나로 다음 위치까지 붙일 수 있으면 큐에서 제거한다. 
        if (curSpot - leakSpots.top() < L)
            leakSpots.pop();
        else
        {
            //L보다 크면 테이프 하나로 커버할 수 있는 구역이 끝났다는 뜻이므로 테이프를 하나 증가시킨다.
            answer++;
            //확인을 시작할 위치를 끊긴 지점으로 바꿔준다. 
            curSpot = leakSpots.top();
            leakSpots.pop();
        }
    }
    
    //위 반복문에서 마지막 위치까지 붙인 테이프 갯수는 포함하지 않기 때문에 마지막으로 쓴 테이프도 더해준다. 
    cout << answer + 1;
    
    return 0;
}