[Greedy] BOJ 2217 번 : 로프

문제

---

N(1≤N≤100,000)개의 로프가 있다. 이 로프를 이용하여 이런저런 물체를 들어 올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.

하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어 올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.

각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다. 단, 각각의 로프는 한 개씩만 존재한다.

 

입력

---

첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 정수이다.

 

 

문제 요약

---

N 개의 구멍이 있는 파이프를 고치려고 한다. 테이프의 길이는 L 이고 구멍을 기준으로 좌우 0.5 의 여유를 두어서 붙여야 한다. 파이프의 최대길이는 1000이고 테이프는 겹치는 것은 가능하지만 잘라서 사용할 순 없다.

 

풀이

---

문제의 요점은 로프의 수가 아무리 많아도 결국 초점은 

가장 약한 로프에 맞추어 진다는 것입니다.

 

예를 들어 최대 중량이 10인 로프와 100인 로프가 있다면 두 개의 로프를 둘 다 사용하였을 때

들 수 있는 가장 큰 무게는 10입니다!.

 

로프 두 개의 최대 중량을 합쳐서 110의 로프를 들려고 한다면

로프 하나의 걸리는 중량은 110/2 = 55 Kg 이 됩니다.

하지만 최대 중량이 10인 로프는 이 무게를 견디지 못하죠!! 

 

따라서 저희는 무게를 배열에 전부 입력받은 후 오름차순으로 정렬 후 

작은 중량부터 볼 겁니다.

 

예를 들어, 

 

5, 10, 15, 20, 25

 

5개의 각기 다른 최대 중량을 갖고있는 로프가 있다고 합시다.

 

가장 작은 값인 5를 기준으로 최대중량을 알고 싶을 때는 

5 * (로프의 전체 갯수)를 하면 됩니다.

 

이유는 가장 약한 로프인 5를 사용해서 최대 중량을 구한다면

로프 하나의 분배되는 중량의 최댓값은 5가 될 겁니다.

 

여기에 로프의 전체 개수를 곱하는 이유는

다른 로프들의 중량은 전부 5보다 크기 때문에

사용이 가능하기 때문이죠.

 

당연히 다음 로프인 10을 사용하면 

분배되는 중량을 10으로 사용할 것이기 때문에

중량 5를 견디는 로프는 사용할 수 없겠죠?

그래서 로프의 개수(cnt)를 하나 줄이는 겁니다.

 

 

 

 

코드

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> rope(n, 0);

	for (int i = 0; i < n; i++)
		cin >> rope[i];
	//로프의 견딜수 있는 무게값을 오름차순으로 정렬
	sort(rope.begin(), rope.end());

	int max = 0;
	int cnt = n;
	for (int i = 0; i < n; i++) {
		//로프의 무게 * 남은 로프의 수
		if (rope[i] * cnt >= max) {
			max = rope[i] * cnt;		
		}
		cnt--;
	}
	cout << max;
	return 0;
}