백준 2217번(그리디)

백준 2217번(그리디)

이 문제는 처음 읽었을 때는 너무 어려웠습니다. 하지만 천천히 문제를 풀다보니 해결책이 보였습니다. 일단 n개의 루프가 주어지니까 w = n*(로프가 견딜수있는 가장 적은무게) 로 놓고 n을 하나씩 빼나가면서 그 중 w의 최댓값을 구했습니다. 사용되는 모든 줄은 w/k의(n개 중 사용된 루프 갯수) 중량을 모두 다 견딜 수 있어야한다는 점에서 생각해낸 풀이법이었습니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	int n;
	int w;
	int maxW = 0;
	int rope;
	vector<int> ropes;

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> rope;
		ropes.push_back(rope);
	}

	sort(ropes.begin(), ropes.end());

	for (int i = n; 0 < i; i--) {
		w = ropes[0] * i;
		if (w > maxW) {
			maxW = w;
		}
		ropes.erase(ropes.begin());
	}

	cout << maxW;

	return 0;
}