[백준] 실버4 : (2217) 로프

문제: https://www.acmicpc.net/problem/2217

 

로프가 5kg, 20kg, 10kg, 15kg이 있다고 하자.

문제에서 가장 높은 질량을 구하고 있으니, 가장 높은 질량을 들 수 있는 로프 순으로 내림차순 정렬을 한다.

내림차순으로 로프를 정렬 후 순회하면, 내가 검사하는 로프와 연결하는 이전 로프들은 무조건 자기 자신보다 높은 질량을 들 수 있다.

 

20kg은 그대로 20kg을 들 수 있다.

 

20kg + 15kg이다.

여러 로프를 사용하여 들면 힘을 똑같이 분배해야 한다.

따라서, 최대 15kg을 들 수 있는 로프에 맞춰 모든 로프가 15kg을 들어야 한다.

똑같이 15kg씩 들면, 총 30kg을 들 수 있다.

 

20kg + 15kg + 10kg이다.

똑같이 10kg씩 들면, 총 30kg을 들 수 있다. 최대 무게와 같다.

 

20kg + 15kg + 10kg + 5kg이다.

똑같이 5kg씩 들면, 총 20kg을 들 수 있다.

 

따라서, '현재 연결을 시도하는 로프 * 이미 연결된 로프'의 무게가 가장 높은 것을 찾으면 된다.

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

int N, Weight;
vector<int> Ropes;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	for (int i = 0, j; i < N; ++i)
	{
		cin >> j;
		Ropes.push_back(j);
	}
	sort(Ropes.begin(), Ropes.end(), greater<int>());

	Weight = Ropes[0];
	for (int i = 1; i < N; ++i)
	{
		int Temp = Weight;
		Weight = max(Weight, (Ropes[i] * (i + 1)));
		if (Temp > Weight) break;
	}

	cout << Weight << "\n";
}