[C++][백준 BOJ]1449_수리공 항승.

문제 번호

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

1449번: 수리공 항승

 

 

알고리즘 분류

그리디(greedy), 정렬(sort)

 

문제 풀이

 구멍난 위치가 가까운 곳부터 먼곳순서로 정렬한다. 문제에서 구멍난곳 양쪽으로 0.5씩 간격이 있어야 한다고 했다.

그래서 (i 번째) + L >= (i+N)번째 +1 의 조건에 만족한다면 i번째에서 시작해서 i+N 번째 까지 같은 테이프로 막을 수 있다고 생각했다. 소수점 계산을 피하기 위해서 0.5씩 필요한 간격을 한쪽으로 몰아준것이다.

 

정렬을 위해서 우선순위 큐를 사용하였다. 

 

전체코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

void Insert(priority_queue<int, vector<int>, greater<int> > &pipe, int N)
{
    for (int i = 0; i < N; i++)
    {
        int num;
        cin >> num;
        pipe.push(num);
    }
}

int Solution(priority_queue<int, vector<int>, greater<int> > &pipe, int L)
{
    int answer = 0;
    int temp = pipe.size();

    while (1)
    {
        answer++;
        int start = pipe.top() + L;

        while (temp != 0)
        {
            if (pipe.top() +1 <= start)
            {
                pipe.pop();
                temp--;
            }
            else
                break;
        }

        if(temp == 0 )
            break;
    }

    return answer;
}

int main()
{
    int N,L; cin >> N >> L;
    priority_queue<int, vector<int> , greater<int> > pipe;

    Insert(pipe,N);
    cout << Solution(pipe,L);

    return 0;
}

 

특이사항

 그동안은 문제풀이를 할때 거의 벡터만 사용했었는데 다른 자료구조, STL을 많이 사용해보아야겠다.