[백준/Baekjoon] 2512 예산 C++ :: Data Structure

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

2512번: 예산

---

1. Logic

- 입력수가 10억을 넘기 때문에 입력만으로 시간복잡도가 터진다. 그래서 시간복잡도가 O(logN)인 자료구조인 priority_queue를 썼다. 그렇기 때문에 시간복잡도  log10억은 9이다. 작은 값부터 탐색해야 하기 때문에 priority queue에 greater인자를 넣어 오름차순으로 정리해주었다.

 

앞의 원소들 부터 차례대로 탐색하면서

1. 입력받은 수의 전체 합이 예산(M)보다 작으면 입력받은 수의 최댓값을 출력한다.

2. 입력받은 수의 전체 합이 예산보다 크면 무조건 상한가를 정해야한다.

2-1. 현재 남은 예산(M)을 처리해야하는 예산의 갯수로 나눈값(N - i)이 현재 처리할 국가의 예산(pq.top())보다 크면 원하는 예산 전체를 지급할 수 있으므로 상한가를 정하지 않아도 된다. 그러므로 남은 예산(M)에서 현재 처리할 국가의 예산값을 빼준다.

2-2. 현재 남은 예산(M)을 처리해야하는 예산의 갯수로 나눈값(N - i)이 현재 처리할 국가의 예산(pq.top())보다 작으면 상한가가 최대 상한가가 구해졌다는 의미이므로 M / (N - i)를 한 값을 출력한다.

---

2. Code

#include<bits/stdc++.h>

using namespace std;

priority_queue<int, vector<int>, greater<int>> pq;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    int n, m;
    int ans;
    long long sum = 0;
    int maxValue = -0x3f3f3f3f;
    cin >> n;

    for(int i = 0; i < n; i++) {
        int a;
        cin >> a;
        
        pq.push(a);
        sum += a;
        maxValue = max(maxValue, a);
    }

    cin >> m;

    if(m < sum) {
        for(int i = 0; i < n; i++) {
            if(m / (n - i) > pq.top()) {
                m = m - pq.top();
            }
            else {
                ans = m / (n - i);
                break;
            }
            pq.pop();
        }
    }
    else {
        cout << maxValue;
        return 0;
    }

    cout << ans;
}

 

 

---

 

 

3. Feedback

각 자료구조 별 시간복잡도를 정확하게 파악하기!

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐