백준 2217번: 로프

[문제 링크]

2217번: 로프

---

k개의 로프를 이용하여 중량이 w인 물체를 들어올릴 때  각각의 로프에는 w/k만큼의 중량이 걸린다고 한다.

 

k개의 로프를 이용하는 경우 들어올릴 수 있는 물체의 최대 중량은 (들 수 있는 무게가 가장 낮은 로프 * k)로 나타낼 수 있다. 

 

따라서, 여러개를 묶었을 때 들 수 있는 최대 중량은 들 수 있는 무게가 가장 낮은 로프에 의해 결정되기 때문에 들 수 있는 무게가 큰 로프 순으로 묶어서 중량을 계산해야 항상 최적해를 얻을 수 있다.

---

#include <iostream>
using namespace std;

int lope[100000];

int max(int a, int b) { return a > b ? a : b; }

void Quick_sort(int start, int end)
{
	if (start >= end) return;

	int pivot = start;
	int i = start + 1;
	int j = end;

	while (i <= j)
	{
		while (i <= end && lope[i] >= lope[pivot])
			i++;
		while (j > start && lope[j] <= lope[pivot])
			j--;

		if (i > j)
		{
			int temp = lope[pivot];
			lope[pivot] = lope[j];
			lope[j] = temp;
		}
		else
		{
			int temp = lope[i];
			lope[i] = lope[j];
			lope[j] = temp;
		}
	}

	Quick_sort(start, j - 1);
	Quick_sort(j + 1, end);
}

int Greedy(int N)
{
	Quick_sort(0, N - 1); // 내림차순 정렬

	int ret = 0;
	for (int i = 0; i < N; i++)
		ret = max(ret, lope[i] * (i + 1));

	return ret;
}

int main(void)
{
	int N;
	cin >> N;

	for (int i = 0; i < N; i++)
		cin >> lope[i];

	cout << Greedy(N) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 110 day