백준 2217번 C++ 풀이

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

2217번: 로프

시간 제한	메모리 제한	solved.ac 티어
2초	192MB	실버4

문제

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

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

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

입력

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

출력

첫째 줄에 답을 출력한다.

---

k개의 로프를 가지고 모두 병렬연결을 진행하면 들 수 있는 최대 중량은 (k개의 로프중에서 가장 짧은 로프의 길이) * k일 것이다.

 

로프가 10, 15, 20, 21이 있다고 하자. 4개를 모두 사용했을 때의 최대 중량은 10 * 4 = 40일 것이다. 그렇다면 10을 빼고 남은 3개로 연결하면 15 * 3일 것이다.

 

이를 일반화해보면 로프길이의 내림차순으로 정렬했을 때 맨 앞의 로프부터 1, 2, 3...을 부여하면 이 번호와 무게를 곱했을때의 값이 그 로프를 포함했을때의 최대 중량이 된다.

 

왜냐하면 위 예제를 다시 사용해보면, 길이 10인 로프만 사용하면 최대 중량은 10이 되고, 21, 20, 10을 사용하면 30이 된다. 어짜피 우리는 최대 중량을 구해야 하기 때문에, 각 로프가 포함되었을 때의 최댓값만을 비교하면 된다.

 

각 로프별로 최댓값을 모두 구했다면, 그 중에서 제일 큰 값을 구하면 된다.

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> rope;

void input() {
    int temp;
    
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> temp;
        rope.push_back(temp);
    }
    sort(rope.begin(), rope.end(), greater<>());
}

void sol() {
    for(int i = 0; i < n; i++) {
        rope[i] *= i + 1;
    }
    cout << *max_element(rope.begin(), rope.end());
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    input();
    sol();
}