[BOJ] 백준 2217번:로프

그리디 문제를 풀어보려 합니다.

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

2217번: 로프

---

문제 설명

로프 문제는 N개의 로프가 버틸 수 있는 중량이 주어집니다.

k개의 로프를 사용하여 중량이 w인 물체를 들어 올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 됩니다.

이때 k개의 로프를 적절히 사용하여 들어올릴 수 있는 중량의 최대는 몇인지 구하는 문제입니다.

---

문제 풀이

먼저 로프의 중량을 정렬합니다.

k개의 로프를 사용하는 경우 각 로프는 최소 w/k만큼 중량을 견딜 수 있어야 하기 때문에, 버틸 수 있는 중량이 큰 로프 먼저 하나씩 사용해봅니다.

i번째 로프 ( 버틸 수 있는 중량의 크기가 i번째로 큰 로프)를 사용하는 경우 들어올릴 수 있는 중량의 최대는 아래와 같습니다. (i번째 이전의 로프들은 i번째보다 버틸 수 있는 중량이 크거나 같기 때문입니다)

즉 모든 로프에 대하여 i번재 로프에서 계산된 최대 중량이 가장 큰 값을 구하는 문제로 바꿀 수 있습니다

시간 복잡도는 O(N)입니다.

---

코드

#include <iostream>
#include <algorithm>
#include <map>
#include <fstream>
#include <string>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int n, arr[100001];
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	sort(arr, arr + n);
	int _max = 0;
	int num = 0;
	int sum = 0;
	for (int i = n - 1; i > -1; i--) {
		num += 1;
		if (_max < arr[i] * num) {
			sum = arr[i] * num;
			_max = arr[i] * num;
		}
	}
	cout << sum;
}