2217 로프

 

greedy 로 풀어봅시다.

 

예를 들어 로프의 정보가 다음과 같이 주어졌다고 합시다.

20 8 15 9 2

 

먼저 내림차순으로 정렬한 뒤, (그렇지 않으면 그리디하게 풀 수 없습니다.)

20 15 9 8 2

생각해봅시다.

 

1) 20

ans = 20

 

2) 20 15

현재 만들 수 있는 최대 중량 = 20

바뀐 최소 값(15)으로 만들 수 있는 최대 중량 = 30

ans = 30

 

3) 20 15 9

현재 만들 수 있는 최대 중량 = 30

바뀐 최소 값(9)으로 만들 수 있는 최대 중량 = 9 * 3 = 27

ans = 30

 

4) 20 15 9 8

현재 만들 수 있는 최대 중량 = 27

바뀐 최소 값(8)으로 만들 수 있는 최대 중량 = 8 * 4 = 32

ans = 32

 

5) 20 15 9 8 2

현재 최소인 값으로 만들 수 있는 최대 중량 = 32

바뀐 최소 값(15)으로 만들 수 있는 최대 중량 = 2 * 5 = 10

ans = 32

 

이렇게 하면 대략적으로 감이 답이 나온 것 같습니다.

그대로 코드로 옮겨보겠습니다.

 

#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
using namespace std;
vector<int> weights;

int main() {  
int n, w;  
scanf("%d", &n);  
for (int i = 0; i < n; ++i) {  
	scanf("%d", &w);  
	weights.emplace\_back(w);  
}  
sort(weights.begin(), weights.end(), greater());

int cnt = 0;
int ans = 0;
for (auto it = weights.begin(); it != weights.end(); ++it) {
    int new_sum = *it * ++cnt;
    if (new_sum > ans) ans = new_sum;
}
printf("%d\n", ans);
return 0;
}