백준 23757번 [아이들과 선물 상자](C++) -yes6686- 티스토리

백준 문제 풀이: 23757 (아이들과 선물 상자)

---

문제 링크: https://www.acmicpc.net/problem/23757

문제 설명:

아이들에게 선물을 나누어주기 위해 **선물 상자에 있는 선물 개수**를 관리합니다. 각 아이가 원하는 선물의 수를 만족시킬 수 있는지 확인해야 합니다.

• 선물 상자에는 선물 개수가 담겨 있습니다.
• 각 아이는 원하는 선물의 개수가 있으며, 그 수를 가져갈 수 있어야 합니다.
• 선물 상자에서 가장 많은 선물을 가지고 있는 상자부터 선물을 나눠줍니다.

모든 아이가 원하는 선물을 만족시키면 **1**을 출력하고, 그렇지 못하면 **0**을 출력합니다.

---

문제 해결 코드

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

int arr[100001]; // 각 아이가 원하는 선물 개수를 저장
priority_queue<int> pq; // 선물 상자 (최대 힙)

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

    int n, m; // n: 선물 상자 개수, m: 아이 수
    cin >> n >> m;

    // 선물 상자의 선물 개수를 입력받아 최대 힙에 저장
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        pq.push(x);
    }

    // 각 아이가 원하는 선물의 수를 입력받음
    for (int i = 0; i < m; i++) {
        cin >> arr[i];
    }

    // 아이들이 원하는 선물을 나누어 줌
    for (int i = 0; i < m; i++) {
        int k = pq.top(); // 가장 많은 선물을 가진 상자 선택
        pq.pop();

        if (k >= arr[i]) { // 원하는 만큼 선물을 나눠줄 수 있다면
            k -= arr[i];
            pq.push(k); // 나머지 선물을 다시 상자에 넣음
        } else {
            // 원하는 만큼 나눠줄 수 없으면 실패
            cout << 0;
            return 0;
        }
    }

    // 모든 아이가 원하는 만큼 선물을 받았다면 성공
    cout << 1;
    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 최대 힙 사용: - priority_queue를 사용하여 가장 많은 선물을 가진 상자를 빠르게 선택합니다.
• 아이들의 요구 처리: - 각 아이가 원하는 선물의 수를 확인합니다.
- 선물을 나눠줄 수 있으면 남은 선물을 다시 힙에 넣습니다.
• 종료 조건: - 선물 상자에 있는 선물이 부족하면 **0**을 출력하고 프로그램을 종료합니다.

시간 복잡도 분석

• **선물 상자 힙 관리:** 최대 힙에서 삽입/삭제는 **O(log n)**입니다.
• **아이들의 선물 요구 처리:** 각 아이에 대해 힙 연산을 수행하므로 **O(m log n)**입니다.
• 전체 시간 복잡도는 **O(n + m log n)**입니다.

---

결과

아이들이 원하는 선물을 모두 나누어줄 수 있는지 확인합니다.

• 입력 예시:

  3 4  
  4 6 8  
  2 4 6 2

• 출력 예시:

  1

• 입력 예시:

  3 4  
  4 6 8  
  2 4 7 2

• 출력 예시:

  0

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!