백준 1449 - 수리공 항승

문제

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

1449번: 수리공 항승

 

풀이

테이프의 수가 최소가 돼야 하니 한 개의 테이프로 겹쳐서 막을 수 있는 곳을 최대한 찾아야 한다.

물을 막을 때 좌 우로 0.5만큼 간격을 필요로 하니 쓸 수 있는 테이프의 길이는 L - 1 이 된다.

물이 새는 곳의 위치를 덱에 정렬하여 저장하고, 덱에 있는 처음 데이터에서 사용 가능한 테이프의 길이를 더 했을 때 나온 값 보다 이하인 것 들은 테이프 하나로 막을 수 있다.

 

예를 들어, 테이프의 길이 L = 2 이고 막힌 곳이 1 2 3 5 이면

좌우 0.5씩 제거하면 L = 1이 되고 구멍 1부터 2까지 1개, 구멍 3 1개, 구멍 5 1개 총 3개가 필요하게 된다.

한 개의 테이프로 막을 수 있는 구멍들을 전부 제거하고 테이프 수를 늘린다.

이 과정을 반복한다.

 

 

소스 코드

C++

#include <iostream>
#include <deque>
#include <algorithm>
 
using namespace std;
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    int N, L;
    cin >> N >> L;
 
    deque<int> v;
 
    for (int i = 0; i < N; i++)
    {
        int num;
        cin >> num;
        v.push_back(num);
    }
 
    sort(v.begin(), v.end());
 
    int result = 0;
 
    int interval = L - 1;
 
    while (v.size())
    {
        int include = v[0] + interval;
        while (v[0] <= include)
        {
            v.pop_front();
            if (!v.size()) break;
        }
        result++;
    }
    
 
    cout << result;
 
    return 0;
}