- n개의 로프가 들 수 있는 최대 무게는 (가장 적게 들 수 있는 로프의 중량)*(로프의 개수)
- 로프의 최대 중량을 내림차순으로 정렬하고, 다음 로프를 사용했을 때 들 수 있는 중량과 현재 중량을 비교해 최대 중량을 구함
- i번 째 로프까지 중량 < i-1번째 로프까지 중량이면 바로 멈춰도 된다고 생각했는데 아래와 같은 반례가 있을 수 있다
Rope (정렬 후)
15
11
9
7
6
최대 중량
15
22
27
28
30
코드
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
vector <unsigned int> Rope;
bool cmp(unsigned int a, unsigned int b) { return a > b; }
int main() {
unsigned int N, l, weight;
// input
scanf("%u", &N);
for (int i = 0; i < N; i++) {
scanf("%u", &l);
Rope.push_back(l);
}
// 내림차순 정렬
sort(Rope.begin(), Rope.end(), cmp);
// 최대 무게 구하기
weight = Rope[0];
for (int i = 1; i < N; i++) {
// i번 째 로프를 사용하여 들 수 있는 무게와 현재까지 들 수 있는 최대 무게 비교
weight = weight > Rope[i] * (i + 1) ? weight : Rope[i] * (i + 1);
}
printf("%u", weight);
return 0;
}
