로프 (백준 - 2217번)

우선, 로프들을 오름차순으로 정렬한 후, 그리디 알고리즘을 이용하여 풀면된다.

O(n^2)를 사용하면 시간초과가 나므로 이점을 유의해서 풀어야한다.

 

정렬 후에 할일은 다음과 같다. 배열 가장 처음에 위치하는 가장 길이가 짧은 로프는 모든 로프의 길이보다 작거나 같으므로 개수는 배열의 크기와 같다. 분기를 타며 길이가 길어질수록 로프의 개수를 하나씩 줄여나가면서 들 수 있는 중량을 구해주면된다. 이전에 저장된 들 수 있는 중량보다 현재 계산한 중량이 더 크다면 그 값으로 덮어쓴다.

 

코드는 다음과 같다.

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

bool cmp(int a, int b)
{
	return a < b;
}

int main()
{
	int input;
	cin >> input;

	int* arr = new int[input];

	int maxLength = 0;
	int maxWeight = 0;

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

	sort(arr, arr + input, cmp);

	for (int i = 0; i < input; ++i)
	{
		maxLength = arr[i];

		if(maxWeight < (input - i) * maxLength)
			maxWeight = (input - i) * maxLength;
	}

	cout << maxWeight << endl;
	delete[] arr;
}