[백준/BOJ] 2217번 로프 (C++)

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

2217번: 로프

 

이 문제의 포인트는 병렬로 로프를 연결했을 때 걸리는 무게의 최대 중량이 가장 낮은 무게를 따라간다는 점이다. 

 

예를들어, 로프가 10, 20, 50 3개가 있다고 가정하자. 세 로프를 병렬로 연결할 경우 각각 최대 중량이 30, 60, 150이다. 이러면 세가지 조건을 모두 만족을 해야하므로, 가장 낮은 무게의 로프인 30까지가 최대 중량이된다. 따라서 로프를 오름차순으로 정렬하고, 작은 로프일수록 병렬 연결을 많이 해주고, 로프가 커질수록 병렬 연결을 안해야한다.

 

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

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, answer = 0;
	cin >> n;
	vector<int> v(n), res(n);
	for(int i = 0; i < n; i++) {
		cin >> v[i];
	}
	sort(v.begin(), v.end());
	for(int i = 0; i < n; i++) {
		answer = max(answer, v[i] * (n - i));
	}	
	cout << answer;
}