백준 2217 로프

www.acmicpc.net/problem/2217

2217번: 로프

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

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

	vector<int>arr(ropecnt+1,0);

	int tmp;
	for (int i = 1; i <= ropecnt; i++)
	{
		cin>>arr[i];
	}
	sort(arr.begin(), arr.end());
	int maxx = -1;

	for (int i =1;i<=ropecnt;i++)
	{
		if (i == 1)
		{
			maxx = arr[ropecnt];
		}
		else
		{
			maxx = max(maxx,arr[ropecnt - i+1] * i);
		}
	}

	cout << maxx;

}

그리디 알고리즘 문제

병렬로 연결하여 (무게/로프의수) 를 통하여 더 무거운 짐을 들 수 있지만, 결국 저 공식의 최대무게는

고른 로프중 (가장 가볍게 드는 로프의 무게)*로프의 수

로 귀결된다.

 

따라서 sort를 통하여 오름차순으로 정렬을 한번 한 뒤에, 무거운 로프부터 한개일때, ... max함수를 통해 값을 비교하였다

단순히 뒤에 두개가 효율적이다고 보기에는 같은 무게의 로프 n개일때는 모든 로프를 사용하는게 더 이득이기 때문이다.