가장 작은 무게를 들 수 있는 로프를 선택해 입력 갯수만큼 곱해주면 땡 아닌가? 라고 생각을 했지만,
문제에 임의로 몇개의 로프를 골라서 사용해도 된다는 말을 보았다.
테스트 케이스 몇개만 생각하면 간단하다.
T1
3
30
15
10
선택
30 => 30x1 =30
30 15 => 15x2 =30
30 15 10 => 10x3 = 30
T2
40
30
15
10
선택
40 => 40x1 = 40
40 30 => 30x2 = 60 (최고무게)
40 30 15 => 15x3 = 45
40 30 15 10 => 10x4 = 40
로프를 무거운 순서대로 정렬해야 탐욕스러운 선택이 가능하므로
정렬 알고리즘만 NlogN 시간의 정렬을 선택해주면 된다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int max(int a, int b){return (a > b ? a : b);}
int cmp(int a, int b) { return a > b; }
int main()
{
int max_w = 0;
int N;
vector<int> rope;
cin >> N;
while (N--)
{
int i;
cin >> i;
rope.push_back(i);
}
sort(rope.begin(), rope.end(),cmp);
int i = 1;
for (auto c : rope)
{
max_w = max(max_w,i*c);
i++;
}
cout << max_w;
return 0;
}
ㅎㅅㅇ