[백준] 2217번 로프

www.acmicpc.net/problem/2217

2217번: 로프

이 문제의 정답률이 42%밖에 되지 않는 이유는 다들 '문제를 제대로 읽지 않아서'인 것 같다.

'모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.'

위 문장만 유의하면 된다.

위의 문장이 없다면 최솟값 * N인데 모든 로프를 사용해야할 필요가 없으므로 여러 가지 경우의 수를 생각해봐야 한다.

만약 입력이 다음과 같이 주어졌을 때

3
10
20
50

모든 로프를 사용해야 한다면 답은 3 * 10 = 30이 되겠지만

모든 로프를 사용해야 할 필요가 없다면 다음과 같은 경우의 수가 있다.

로프 3개를 쓴다면 들 수 있는 최대 중량은 10 * 3 = 30

로프 2개를 쓴다면 들 수 있는 최대 중량은 20 * 2 = 40

로프 1개를 쓴다면 들 수 있는 최대 중량은 50 * 1 = 50

이므로 답은 50이 된다.

따라서 로프가 버틸 수 있는 중량을 벡터에 입력받은 후 오름차순으로 정렬한 후 하나 씩 제외하면서 최댓값을 구했다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int n;
	vector<int> v;
	cin >> n;
	int weight;
	for (int i = 0; i < n; i++) {
		cin >> weight;
		v.push_back(weight);
	}
	sort(v.begin(), v.end());
	int maxWeight = 0;
	for (int i = 0; i < n; i++) {
		if (v[i] * (n - i) > maxWeight) {
			maxWeight = v[i] * (n - i);
		}
	}
	cout << maxWeight;
	return 0;
}