백준 2217번 - 로프

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

N 제한을 보면 O(N^2)만 하더라도 바로 시간초과에 걸리는 것을 알 수 있다.

접근 방법을 생각하다가 각각의 로프에 모두 동일한 중량이 가해진다는 것을 생각해서 바로 해결했다.

로프 마다 버틸 수 있는 중량을 오름차순으로 먼저 정렬한다.

첫 번째의 로프의 최대 중량으로 계산한다면 

(첫 번째 로프가 견딜 수 있는 무게) * (N) 이 견딜 수 있는 중량의 합이 될 것이다.

두 번째의 로프의 최대 중량으로 계산한다면 

(두 번째 로프가 견딜 수 있는 무게) * (N-1) 이 견딜 수 있는 중량의 합이 될 것이다.

이와 같은 방법으로 N번째 까지 중량의 합을 계산 하면서

최대 중량을 구하면 문제를 해결할 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main(){
    
    int N;
    cin>>N;
    
    vector<int> vec(N,0);
    for(int i=0;i<N;i++)
        scanf("%d",&vec[i]);
    
    sort(vec.begin(),vec.end());
    
    int ans=0;
    for(int i=0;i<N;i++)
        ans=max(ans,vec[i]*(N-i));
    
    cout<<ans<<endl;
    
    return 0;
}