로프

문제

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

해당 문제는 입력으로 주어진 각각의 로프를 활용하여 들어올릴 수 있는 물체의 최대 중량을 출력하는 문제이다.

특이사항으로는 로프를 하나만 사용할 수도 있지만, 여러 로프를 병렬로 연결할 수도 있는 점이다.
단, 로프를 병렬로 활용하는 경우에는 사용하는 로프 중 가장 적은 무게를 들 수 있는 로프가 기준이 된다.
예를 들면 k개의 로프를 활용하여 물건을 들어올리는 경우, k개의 로프 중 들어올릴 수 있는 최소 무게가 A라면, 해당 경우에는 kA의 무게를 들어올릴 수 있다.

이러한 특이사항을 고려하여 그리디 알고리즘 접근을 하면 다음과 같이 풀 수 있다.
1) 주어진 입력 로프의 중량을 기준으로 정렬
2) 위의 특이사항을 유의하며, 가장 많은 중량을 들 수 있는 로프를 1개만 사용하는 경우부터 여러개를 사용하는 경우를 탐색

이를 고려한 전체 코드는 다음과 같다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	//freopen("input.txt", "rt", stdin);

	int n, temp;
	int max = -2147000000;
	vector<int> w_list;

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> temp;
		w_list.push_back(temp);
	}

	sort(w_list.begin(), w_list.end());

	for (int i = n - 1; i >= 0; i--) {
		if (w_list[i] * (n - i) > max) {
			max = w_list[i] * (n - i);
		}
	}

	cout << max << "\n";
	return 0;
}