[C++] 백준 2217번 로프

그리디 알고리즘 문제입니다.

로프로 가장 들 수 있는 가장 큰 중량을 구하는 문제입니다.

15kg을 들 수 있는 밧줄 한개로는 최대 15kg을 들 수 있습니다.
10kg을 들 수 있는 밧줄 한개로는 최대 10kg을 들 수 있습니다.

15kg로프와, 10kg로프를 같이 사용해서는 25kg을 들 수 있어야 하지만
10kg로프는 12.5kg을 들 수 없기때문에 kg이 적은 로프에 맞춰진다고 생각할 수 있습니다.
그러므로 15kg과 10kg로프를 같이 사용하면 10 * 2이므로 20kg을 들 수 있습니다.

가장 큰 무게를 들 수 있는 로프부터 계산을 합니다.

maxWeight = max(maxWeight, lope[i] * (i + 1));

= 현재 로프의 무게 * 로프의 개수
가장 큰 무게를 들 수 있는 것을 maxWeight에 넣어서 출력합니다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#define fio ios_base::sync_with_stdio(0), cin.tie(0)
using namespace std;

int lope[100010];

int main(int argc, char *argv[])
{
	int n;
	int maxWeight = 0;

	memset(lope, 0, sizeof(lope));

	cin >> n;

	for (int i = 0; i < n; ++i) {
		cin >> lope[i];
	}

	sort(lope, lope + n, greater<int>());

	for (int i = 0; i < n; ++i) {
		maxWeight = max(maxWeight, lope[i] * (i + 1));
	}

	cout << maxWeight << endl;

	return 0;
}