[백준] 2217번 로프 -C++

문제

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

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

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

입력

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

출력

첫째 줄에 답을 출력한다.

예제 입력 1

2
10
15

예제 출력 1

20

예제 1:

10kg, 15kg을 버티는 2개의 로프에 5,5 씩 중량 할당 가능 6, 6씩 중량 할당 가능…10,10 할당 가능, 11, 11부터는 할당이 불가 → 10,10이 가장 최대로 들 수 있는 중량 →20kg

---

문제 요약:

로프를 병렬로 연결했을 때, 각각의 로프에 모두 고르게 w/k의 중량이 걸릴 때, 최대로 들 수 있는 중량 구하기

최대로 들 수 있는 중량 :
k개의 로프 중 버틸 수 있는 중량이 가장 작은 로프의 버틸 수 있는 중량 * k개 이다.

풀이 방법:

1. 로프의 갯수 N, 로프의 중량을 담은 벡터 rope 입력받기

2. 벡터 rope의 중량들을 오름차순 정렬

3. 정렬된 벡터에서 버틸 수 있는 무게가 가장 낮은 중량의 로프 i의 무게 rope[i] 와

   i 로프가 가장 낮은 중량인 로프의 개수 n-i를 곱해 최대값을 찾는다.

n - i : 인덱스는 0부터 시작이니까 자기보다 큰 용량의 로프 개수 + 자기 자신

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

int main(){
    int N;
    cin >> N;
    vector<int> rope(N);
    int answer = 0;

    // 로프의 무게 입력받기
    for(int i = 0; i < N; ++i) {
        cin >> rope[i];
    }
    //무게 오름차순 정렬
    sort(rope.begin(), rope.end()); 
    
    // 각 로프를 사용할 때의 최대 무게 계산
    for(int i = 0; i < N; ++i) {
        answer = max(answer, (N - i) * rope[i]); 
    }
    cout << answer << endl;
    
    return 0; 
}