<백준> 2217번 로프

문제

N(1≤N≤100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.

하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.

각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다. 단, 각각의 로프는 한 개씩만 존재한다.

출처:https://www.acmicpc.net/problem/2217

문제 풀이:

- 그리디 알고리즘

- 병렬로 연결할 경우 w/k 만큼 중량이 걸리게 되는데 로프는 각각 들 수 있는 물체의 중량이 서로 다르므로 가장 적은 중량을 들고 있는 로프의 무게 A와 로프의 수를 곱한값이 최대 중량이다.

- 단 임의로 몇개의 로프를 골라서 사용할 수 있으므로 가장 작은 중량의 로프부터 차례대로 없애가며 값을 계산하여 들어 올릴수 있는 최대 중량을 구해낸다.

- 우선 순위 큐를 이용하여 오름차순으로 정렬.

- 먼저 기본값으로 가장 작은 중량을 들 수 있는 로프를 기준으로 중량 계산

- 그 이후 큐가 빌때까지 가장 작은 중량을 들 수 있는 로프를 하나씩 없애며 중량을 계산하고 가장 큰 값을 구한다.

#include<iostream>
#include<algorithm>
#include<queue>
#include<functional>
using namespace std;
 
int main() {
    priority_queue<int,vector<int>,greater<int>> q;
    int N;
    int temp;
 
    scanf_s("%d", &N);
 
    for (int i = 0; i < N; i++) {
        scanf_s("%d", &temp);
        q.push(temp);
    }
 
    int w = q.top();
    int ans = w * q.size();
    q.pop();
    
    while (!q.empty()) {
        w = q.top();
        int Qans=w*q.size();
        q.pop();
 
        if (Qans > ans) {
            ans = Qans;
        }
    }
 
    cout << ans << endl;
}