백준 2217 - 로프

문제

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

2217번: 로프

 

풀이

입력받은 N개의 수를 정렬하여 저장한다.

최대 중량을 구해야 하므로 정렬된 값들을 골라서 최대로 만들면 된다.

 

정렬된 다음 인덱스 로프는 이전 인덱스 로프 무게를 버틸 수 있다.

따라서 첫 번째 값은 최대 N배만큼 늘릴 수 있고, 두 번째 값은 N - 1배, 세 번째는 N - 2배... 이렇게 각 로프들을 최대 중량으로 바꾼다.

예를 들어 10 15 17 19 면 10*4 15*3 17*2 19*1 이 되므로 40 45 34 19가 되고 이중 최대는 45가 된다. 

 

소스 코드

C++

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    int N;
    cin >> N;
 
    vector<int> v;
 
    for (int i = 0; i < N; i++)
    {
        int num;
        cin >> num;
        v.push_back(num);
    }
 
    sort(v.begin(), v.end());
 
    int mul = v.size();
    std::priority_queue<int> pq;
    for (int i = 0; i < N; i++)
    {
        pq.push(v[i] * mul--);
    }
 
    cout << pq.top();
 
    return 0;
}