[백준 알고리즘] 2217번: 로프

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

문제

문제

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

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

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

입력

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

출력

첫째 줄에 답을 출력한다.

풀이

혼자 끙끙대다가 인터넷을 찾아보고 풀었다. 문제의 핵심은 k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다. 라는 조건에 있다. 만약 어떤 로프 여러개가 연결되어 있을 때, 이 로프들이 끊어지는 순간은 버틸 수 있는 최대 중량이 가장 작은 로프의 최대 중량이 된다. 예를 들어 10, 15, 20 이 모두 연결되어 있다면, 각각의 로프는 w / 3 의 중량을 받게된다. 물건의 무게가 무거워지면 무거워질 수록 최대 중량이 가장 작은 로프가 먼저 끊어지게 될 것이기 떄문에, 이 조합에서의 최대 중량 w는 w / 3 이 10에 도달하게 되는 순간의 값이고, 따라서 w 는 30이 된다.

위 규칙을 더 효율적으로 이용하는 방법은 그리디 알고리즘을 사용하는 것이다. 어차피 우리는 최대 중량이 가장 작은 로프로 계산을 하게 되고, 이 로프의 값이 크면 클 수록 최대 중량이 커지기 때문에 로프의 중량을 내림차순으로 정렬한 뒤 하나씩 추가하면서 최대 중량을 구할 수 있다.

코드

' '
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

int main (){
    int N;
    vector<int> ropes;

    scanf("%d", &N);

    while(N--){
        int w;
        scanf("%d", &w);

        ropes.push_back(w);
    }

    sort(ropes.begin(), ropes.end(), greater<int>());

    int maxWeight = 0;
    int connectCount = 0;
    for (int i = 0 ; i < ropes.size() ; i++){
        connectCount++;
        maxWeight = max(maxWeight, ropes[i] * connectCount);
    }

    printf("%d", maxWeight);
}