백준 12788번 [제 2회 IUPC는 잘 개최될 수 있을까?](C++) -yes6686- 티스토리

백준 문제 풀이: 12788번 [제 2회 IUPC는 잘 개최될 수 있을까?]

---

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

문제 설명:

제2회 IUPC를 위해 필요한 공책의 총 수를 계산하고, 제공 가능한 공책을 가진 사람들 중 최소한의 인원으로 충족시킬 수 있는지 판단하는 문제입니다. 공책이 충분하다면 최소 인원을 출력하고, 부족하다면 "STRESS"를 출력합니다.

---

문제 해결 코드

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

int arr[1001]; // 각 사람이 제공할 수 있는 공책 수

// 내림차순 정렬을 위한 비교 함수
bool compare(int a, int b) {
    return a > b;
}

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

    int n; // 사람의 수
    cin >> n;

    int m, k; // 팀 수와 팀당 필요한 공책 수
    cin >> m >> k;

    int t = m * k; // 총 필요한 공책 수
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    int ans = 0; // 필요한 최소 사람의 수
    sort(arr, arr + n, compare); // 공책 수를 내림차순으로 정렬

    // 필요한 공책을 충족할 수 있는 최소 인원 계산
    for (int i = 0; i < n; i++) {
        t -= arr[i];
        ans++;
        if (t <= 0) {
            break; // 필요한 공책이 모두 충족되면 종료
        }
    }

    if (t > 0) {
        cout << "STRESS" << '\n'; // 공책이 부족한 경우
    } else {
        cout << ans; // 최소 인원 출력
    }
}

---

코드 설명

위 코드는 공책이 충분히 제공될 수 있는지 확인하고, 필요한 최소 인원을 계산합니다. 주요 로직은 다음과 같습니다:

1. 입력 처리: 각 사람이 제공할 수 있는 공책 수를 배열에 저장합니다.
2. 정렬: 많은 공책을 제공할 수 있는 사람을 우선적으로 사용하기 위해 내림차순 정렬합니다.
3. 충족 여부 확인: 공책을 차례로 차감하며 필요한 인원을 계산하고, 필요한 공책이 충족되면 종료합니다.

시간 복잡도:

• 정렬: O(N log N), N은 사람의 수
• 공책 사용 계산: O(N)

전체 시간 복잡도는 O(N log N)입니다.

---

결과

위 코드는 주어진 입력에 따라 공책을 충분히 충족할 수 있는지 판단하며, 최소 인원을 출력하거나 "STRESS"를 출력합니다. 최적화나 대체 구현 방안이 있다면 댓글로 의견을 남겨주세요!