[Algorithm] 백준 - 풍선 공장 (15810번)

문제

[백준] 풍선 공장

 

 

사용 알고리즘

- 이분 탐색

해결방법

• 스텝별로 실시간 누적 작업시간을 담는 우선순위 큐를 활용한다

• 우선순위 큐에 <누적작업시간, 필요작업시간> pair를 삽입한다. 이렇게 하면 가장 작업이 빨리 끝나는 스태프가 항상 top 에 위치하기 때문에, 해당 스태프를 Pop 한 뒤, 작업을 할당해서 다시 push 해주면 된다.
• 예제 1을 살펴보면, 
  • 가장 빠르게 풍선 1개를 완성한 (3, 3) 스태프를 Pop 하고, 해당 스태프에게 작업을 한 번더 할당한 뒤 (6, 3) 을 push 해준다.
  • 그 다음으로 빠르게 풍선 1개를 완성한 (5, 5) 스태프를 pop하고, 일을 할당한 뒤 (10, 5)를 push 한다.
  • 그 다음으로 빠르게 풍선 1개를 완성한 (6, 3) 스태프를 pop하고, 일을 할당한 뒤 (9, 3)를 push 한다.
  • . . .
  • 필요한 M개째의 풍선을 완성한 스태프 (14, 7)를 pop 하고, 해당 스태프의 누적 작업시간을 구하면 그게 답이된다.

예제 1

소스코드

사용언어 : C++

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pa;

int N, M;

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

    cin >> N >> M; // 스탭 수, 풍선 수

    priority_queue<pa, vector<pa>, greater<pa>> pq;

    for (int i=0; i<N; i++) {
        ll v;
        cin >> v;
        pq.push(make_pair(v, v)); // 실시간 누적 작업시간 / 스탭별 필요 작업시간
    }

    for (int i=0; i<M-1; i++){
        ll now_time = pq.top().first;
        ll staff_time = pq.top().second;

        pq.pop();
        pq.push(make_pair(now_time + staff_time, staff_time));
    }

    cout << pq.top().first;
    
    return 0;
}

우선순위 큐 (Priority_Queue)

https://kbj96.tistory.com/15

* 우선순위에 따라 정렬된 큐

* 어떤 원소가 삽입되면, 주어진 우선순위에 맞춰서 큐가 정렬된다.

* Heap 으로 구현됨 >> 정렬 시 O(log n) 소요

chatGPT

* 우선순위 큐는 기본적으로 내림차순이므로, 오름차순 정렬을 하고 싶다면, 우선순위 큐의 템플릿 매개변수로 비교 연산자를 사용한다

>> priority_queue<자료형, vector<자료형>, greater<자료형>> 변수명;

 

 

한줄평

조만간 힙 자료구조를 따로 정리해야겠다