[백준][C++] 23757: 아이들과 선물 상자

 

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

23757번: 아이들과 선물 상자

 

 

 

 

 

---

- 문제

 

  N개의 선물 상자에 각각 c개의 선물이 들어 있고, M명의 아이들이 각자 w개의 선물을 받고 싶을 때 아이들이 주어진 순서대로 선물을 고를 때 모든 아이들이 선물을 받을 수 있는지 없는지 판별하는 문제다.

 

 

---

- 해설

https://stopthebackspace.tistory.com/123

 

위의 링크에서 우선순위 큐를 처음 사용해 보았고, 어떻게 사용해야 하는지 배웠기에, 큰 숫자가 먼저 튀어나오도록 우선순위큐를 만들어 사용하면 문제를 풀 수 있다.

 

 

나는 처음에 아이들까지도 우선순위큐로 정렬했었는데, 문제를 보니 1번 아이부터 M번 아이까지 한 번에 한명씩 가져간다고 되어 있어서, 얘네는 정렬할 필요가 없다는 것을 느끼고 일반 큐로 바꿔보니 정답이 되었다.

 

그렇다면, 여기선 안 바꿨지만 굳이 반복문을 3개 쓸 필요 없이 2번째 반복문, cin >> temp를 할때 바로 적용하면 더 빠르게 문제를 해결할 수 있을 것 같다. 

 

---

- 풀이

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

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

    int N, M, temp;
    bool isDone = true;
    priority_queue<int, vector<int>, less<int>> box;
    queue<int> present;
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        cin >> temp;
        box.push(temp);
    }
    for (int i = 0; i < M; i++)
    {
        cin >> temp;
        present.push(temp);
    }
    while (!present.empty())
    {
        temp = box.top() - present.front();
        if (temp > 0)
        {
            box.pop();
            box.push(temp);
            present.pop();
        }
        else if (temp == 0)
        {
            box.pop();
            present.pop();
        }
        else
        {
            isDone = false;
            break;
        }
    }
    if (isDone)
    {
        cout << 1;
    }
    else
    {
        cout << 0;
    }

    return 0;
}

 

 

---

- 새롭게 알게 된 점