[백준] No.17612 - 쇼핑몰 (C++, 우선순위 큐)

문제

 

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

17612번: 쇼핑몰

 

풀이

 

solved.ac 난이도: Gold 1

 

각 계산대에 줄을 세우는 우선순위 큐와 계산을 끝내고 빠져나오는 순서를 저장하는 우선순위 큐의 정렬 순서가 중요한 문제이다.

 

각 계산대에 줄을 세우는 우선순위 큐를 생각해보자.

고객들은 계산대의 대기 시간이 가장 작은 곳에 줄을 서고, 만약 대기 시간이 같은 계산대가 여러 개라면 번호가 작은 계산대에 줄을 선다.

따라서 우선순위 큐는 대기 시간과 계산대 번호, 두가지 정보를 저장해야 한다.

priority_queue<pair<int,int>,vector<pair<int,int>>, greater<pair<int,int>> > min_pq

 

이 우선순위 큐의 정렬 순서는 대기 시간이 작은 것이 위로,  대기 시간이 같다면 계산대 번호가 작은 것이 위로 가도록 만들어야 한다.

따라서 greater<pair<int,int>> 순서인 최소 힙으로 구현해준다.

 

일단 계산대는 고객이 비어있는 상태이기 때문에 계산대의 개수(counter_num)만큼의 고객을 일단 번호가 작은 계산대에서부터 순서대로 줄을 세우자.

줄은 PIPO의 순서(선입 선출)에 해당하므로 queue에 줄을 선 고객의 번호와 고객의 물건 수(item_num)를 저장한다.

=> vector<queue<pair<int,int>>> lines;

 

각각의 고객의 물건 수(item_num)와 줄을 선 곳(i)의 정보를 min_pq에 저장한다.

int customer_idx, item_num ;
bool pass = false;
 
for(int i=0; i<counter_num ; ++i ){ //줄 세우기
 
  if(i >= customer_num ){
    pass = true;
    break;
  }
      
  scanf("%d %d", &customer_idx, &item_num);
  lines[i].push(make_pair(item_num, customer_idx));
  min_pq.push(make_pair(item_num, i));
}

 

이때 고객의 수보다 계산대의 수가 더 많은 경우를 예외 처리하기 위해

i가 고객의 수를 넘으면 break 해주자.

 

이제 각 계산대에 한 사람 씩 줄을 서고 있다.

대기 시간이 가장 작은 줄의 정보는 min_pq.top().second 에 존재한다.

따라서 min_pq.top()을 이용해 줄을 세우고 이제 그 줄의 새로운 대기 시간(waiting_time)은 

줄을 선 고객의 물건 수(item_num) + 해당 줄의 대기 시간이다.

waiting_time = min_pq.top().first + item_num;

 

줄을 선 고객의 정보를 각 lines에 저장하고 사용된 min_pq.top()은 pop을 해주고,

이제 새로운 줄의 정보(해당 줄의 대기시간 와 줄의 번호)는 min_pq에 삽입하여 다음 최소 대기 시간의 줄을 찾아간다.

 

 

int line_idx, waiting_time;
if(!pass)
for(int i=counter_num ; i<customer_num ; ++i){
  scanf("%d %d", &customer_idx, &item_num);
 
  line_idx = min_pq.top().second;
  waiting_time = min_pq.top().first + item_num;
 
  lines[line_idx].push(make_pair(waiting_time, customer_idx));
  min_pq.pop();
  min_pq.push(make_pair(waiting_time, line_idx));
} //줄 세우기 끝

 

이제 모든 줄 세우기 작업이 끝났다.

 

 

 

다음은 빠져나가는 순서를 저장하는 우선순위 큐를 생각해보자.

가장 먼저 빠져나가는 고객은 모든 줄의 앞 고객들 중 waiting_time(대기 시간)이 가장 작고, 만약 waiting_time이 같다면

계산대의 번호(줄의 번호)가 가장 큰 고객이다.

 

따라서 우선순위 큐를 waiting_time이 작은 순, 만약 waiting_time이 같으면 줄의 번호(line_idx)가 큰 순서대로 정렬하도록 구현한다.

해당 정렬은 stl에서 지원하지 않기 때문에 직접 구현해주자.

priority_queue<pair<int,int>,vector<pair<int,int>>, cmp > result_pq;

 

struct cmp {
 
  bool operator()(pair<int, int>&a, pair<int, int>&b) {
    if (a.first == b.first) 
      return a.second < b.second;
    else
      return a.first > b.first;
  }
 
};

 

 

이제 줄을 세웠던 것과 동일하게 일단 각 줄의 맨 앞의 고객의 정보로 result_pq를 구성하자.

 

long long result =0;
  for(int i=0; i<counter_num ; ++i ){ //빠져나가는 순서 찾기
 
    if(i >= customer_num )
      break;
    result_pq.push(make_pair(lines[i].front().first, i));
  }

 

이제 result_pq.top()이 가장 먼저 계산의 끝마치는 고객의 정보가 된다.

이 정보로 출력 값(result)을 계산해주고 해당 top은 큐에서 pop(해당 고객은 빠져나감)한다.

또한 해당 고객은 줄의 맨 앞에 서 빠져나왔으므로 front를 pop 해주고 해당 줄이 비어있지 않다면 다음 고객의 정보를 result_pq에 삽입하는 과정으로 출력 값을 계산 가능하다.

 

 

for(int i=1; i<=customer_num ; ++i){
 
  line_idx = result_pq.top().second; 
 
  customer_idx = lines[line_idx].front().second;
  result = result + ( (long long)i*(long long)customer_idx);
  result_pq.pop();
  lines[line_idx].pop();
 
  if(!lines[line_idx].empty())  //해당 계산대에 줄이 있는 경우만
    result_pq.push(make_pair(lines[line_idx].front().first,line_idx));
}

 

본인의 경우 result만은 long long형으로 선언하였는데 

계산에 사용되는 customer_idx는 i와 곱셈 시 int형의 범위를 초과하기 때문에 각 연산 전에 미리 long long형으로 형 변환을 해주지 않아 계속 오답이 나왔다.

 

항상 오버 플로우에는 주의하자.

 

코드