BOJ/백준 - 2217 로프 C++

처음 코드에서 시간초과가 나면서 문제 접근에서 좀 생각했던 문제다.

 

예제를 보면, 각각 10, 15의 중량을 견딜 수 있는 2개의 로프로 들어올릴 수 있는 최대 무게는 20이다.

각 로프에는 고르게 w/k만큼의 중량이 걸리게 된다는 조건에서 힌트를 얻어서

오름차순으로 정렬하여 로프가 견딜 수 있는 중량 * (N-1)를 해주면서 문제를 해결하였다.

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
vector <int> v;
 
int main() {
 
    //시간 줄이기
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
 
    int N;
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        int tmp;
        cin >> tmp;
        v.push_back(tmp);
    }
    
    sort(v.begin(), v.end());
 
    int max = 0;
    for (int i = 0; i < N; i++) {
        int num = v[i] * (N-i);
        if(max<num){
            max = v[i] * (N-i);
        }
    }
 
    cout << max; 
 
    return 0;
 
}