[BOJ 2217] 로프

그리디 알고리즘 분류로 되어있는데, 정확한 분류 사유는 모르겠다.

 

 

 

이 문제를 풀기 위해서는 w의 물건을 들기 위해서 k개의 로프를 사용했다면, 각 로프에 w/k의 하중이 걸린다.

 

 

 

로프마다 견딜 수 있는 무게를 오름차순으로 정렬했다고 하면,

 

 

 

(각 로프가 견딜 수 있는 최대 하중) * (사용할 수 있는 로프의 개수)로 최댓값을 찾으면 된다.

 

 

 

해설코드(C++).

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
long long N, val;
long long sum = 0;
vector<long long> v;
 
int main() {
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> val;
        v.push_back(val);
    }
    sort(v.begin(), v.end());
    
    for(int i = 0; i < v.size(); i++){
        sum = max(sum, v[i] * (N - i));
    }
    
    cout << sum << endl;
    return 0;
}