문제를 이해하는데 시간이 꽤 걸린 문제이다.
예를 들어 각각 최대 3, 5, 4, 2, 1의 중량을 버틸 수 있는 로프 A, B, C, D, E가 있다고 하고, 들어올릴 물체의 중량을 w라 하자. 문제에서 모든 로프를 사용해야 할 필요가 없다고 했으므로 물체를 들어올리는 방법을 다섯 가지로 나눌 수 있다.
로프 다섯 개를 모두 사용하는 경우
문제에서 각각의 로프에는 모두 고르게 (물체의 중량) / (사용하는 로프의 개수)만큼의 중량이 걸린다고 제시되었으므로 로프마다 걸리는 중량은 w/5이다.
만약 하나의 로프라도 자신이 버틸 수 있는 중량보다 더 큰 중량을 들어올려야 하는 경우 그 로프는 끊어진다.
물체의 중량 w=13이라 해보자. 그러면 각 로프가 들어올려야 할 중량은 13/5=2.6이다. 로프 A, B, C는 각각 3, 5, 4의 중량을 버틸 수 있으므로 로프가 끊어지지 않는다. 그러나 로프 D, E는 버틸 수 있는 중량보다 들어올려야 할 중량이 더 크기 때문에 끊어질 것이다.
따라서 각 로프가 들어올려야 할 중량은 버틸 수 있는 중량이 가장 작은 로프가 최대로 버틸 수 있는 중량이 되어야 한다.
이를 식으로 표현하면 (물체의 중량) / (사용하는 로프의 개수) = min(로프 별 버틸 수 있는 중량)이다.
따라서 로프 다섯 개를 모두 사용할 때 들어올릴 수 있는 물체의 중량의 최댓값은 1*5=5이다.
버틸 수 있는 중량이 최소인 로프를 찾아야 하므로 로프를 오름차순으로 정렬해놓는 것이 좋다.
로프 네 개만 사용하는 경우
다섯 개의 로프 중 네 개를 골라, 위에서와 동일한 방식으로 계산하면 된다.
그러나 네 개의 로프를 고르는 모든 경우에 대해 실행할 필요가 없다. 왜일까?
{1, 3, 4, 5}를 골랐을 때와 {2, 3, 4, 5}를 골랐을 때를 비교해보자. {1, 3, 4, 5}를 골랐을 때 들어올릴 수 있는 최대 중랑은 14=4이고, {2, 3, 4, 5}를 골랐을 때 들어올릴 수 있는 최대 중랑은 24=8이다.
여기서 우리는 로프들을 가능한 큰 값들로 골라야 한다는 것을 알 수 있다. 로프들을 미리 정렬해 놓았으므로, 로프 배열의 뒤에서부터 가장 큰 로프 네 개를 고르면 된다.
따라서 로프 네 개를 사용할 때 들어올릴 수 있는 물체의 중량의 최댓값은 2*4=8이다.
로프 세 개만 사용하는 경우
2에서와 동일한 방법으로 계산한다. 로프 {3, 4, 5}를 사용해 3*3=9의 물체를 들어올릴 수 있다.
로프 두 개만 사용하는 경우
로프 {4, 5}를 사용해 2*4의 물체를 들어올릴 수 있다.
로프 하나만 사용하는 경우
로프 5를 사용해 1*5의 물체를 들어올릴 수 있다.
구현
#include <iostream>
#include <vector>
#include <algorithm> // sort
#define MAX(X, Y) (((X) > (Y)) ? (X) : (Y))
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, i, w, tmp;
vector<int> v;
cin >> N;
for (i = 0; i < N; i++) {
cin >> tmp;
v.push_back(tmp);
}
sort(v.begin(), v.end());
w = 0;
for (i = 0; i < N; i++) {
tmp = (N - i) * v[i];
w = MAX(w, tmp);
}
cout << w << endl;
return 0;
}