[백준 19640] 화장실의 규칙

www.acmicpc.net/problem/19640

19640번: 화장실의 규칙

우선순위 큐를 사용하는 문제이다.

eazymean.tistory.com/99

[c++] STL priority_queue 우선순위 큐

 

화장실 줄이 m개이고 각 줄의 맨 앞은 우선순위 조건에 따라 한명씩 화장실에 들어간다.

줄이 빠진 줄은 다음 줄에 서있던 사람이 줄을 채운다.

 

이 과정을 반복하는데 k번째 사람이 몇번째에 화장실에 들어가게 되는지에 대한 문제이다.

 

1. 화장실 문앞에 있는 m개 줄에 대해 우선순위 큐를 사용하여 pop한다.

2. pop한 사람이 k번째 사람이라면 -> break

3. 아니라면 해당 줄에 있던 사람을 채운다.

 

해당 줄에 있던 사람을 채우고 + tle가 나지 않기 위해 처음 구조체를 선언할때 row와 col정보를 저장한다.

구조체 벡터에 row와 col정보를 저장하여 해당 row의 col+1에 해당하는 사람을 우선순위 큐에 푸쉬한다.

 

#include <stdio.h>
#include <queue>
using namespace std;
int n, m, k;

struct p
{
  int idx, row, col, day, hurry;
};

bool operator<(const p &t1, const p &t2)
{
  if (t1.day == t2.day)
  {
    if (t1.hurry == t2.hurry)
    {
      return t1.row > t2.row;
    }
    return t1.hurry < t2.hurry;
  }
  return t1.day < t2.day;
}

// struct cmp
// {
//   bool operator()(p &t1, p &t2)
//   {
//     if (t1.day == t2.day)
//     {
//       if (t1.hurry == t2.hurry)
//       {
//         return t1.row > t2.row;
//       }
//       return t1.hurry < t2.hurry;
//     }
//     return t1.day < t2.day;
//   }
// };

priority_queue<p> pq;
vector<p> v[100000];
int main(void)
{
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 0; i < n; i++)
  {
    int d, h;
    scanf("%d%d", &d, &h);
    int row = i % m;
    int col = i / m;
    v[row].push_back({i, row, col, d, h});
  }

  //pq 초기화
  int i = 0;
  for (i = 0; i < m; i++)
  {
    if (v[i].size() >= 1)
    {
      pq.push(v[i][0]);
    }
  }

  int cnt = 0;

  while (1)
  {
    p cur = pq.top();
    if (cur.idx == k)
    {
      break;
    }
    pq.pop();
    int row = cur.row;
    int col = cur.col;

    if (col < v[row].size() - 1)
    {
      pq.push(v[row][col + 1]);
    }
    cnt++;
  }

  printf("%d\n", cnt);
  return 0;
}