[Greedy] 2217번 로프

2217번 로프

 

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

 

문제

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

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

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

 

입력

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

 

출력

첫째 줄에 답을 출력한다.

 

예제 입력

3
2 10 15

4
3 11 5 4

 

예제 출력

20

12

 

해결방법

Greedy Algorithm 유형의 문제이다

 

 

⭐️ 솔루션 ⭐️

• 내림차순 정렬 후, 중량이 높은 로프 순서대로 하나씩 포함시키며 최대 중량을 확인해야한다

• 만약 도중 중량을 버티지 못하고 로프가 끊어져도 기존의 로프를 버릴 이유가 없다. 이는 기존 로프가 아닌 새로 추가한 로프가 약한것이기 때문에 새로추가한 로프만 버리면 된다
• 또한 최대 중량은 연속된 로프일 때 나온다. 내림차순으로 정렬했기 때문에 비연속적인 로프의 경우는 최적해가 될 수 없다

 

시간 복잡도

이를 순열로 접근한다면 어마어마한 시간이 발생되지만 내림차순 정렬 후, 하나씩 포함시키는 솔루션을 적용한다면 O(N) = 100,000 의 시간복잡도를 가지게된다

 

 

 

소스코드

문제 해결 시간 : 50m

메모리 : 2884 KB

시간 : 16 ms

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

int n,in;
int ans;
vector<int> lope;

bool cmp(int a, int b){
    return a > b;
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> in;
        lope.push_back(in);
    }
    
    // 내림차순 정렬
    sort(lope.begin(), lope.end(), cmp);
    
    // 최대 중량
    ans = lope[0];
    
    for(int i=1; i<lope.size(); i++){
        // 현재 로프를 포함할 때의 중량
        int weight = lope[i] * (i+1);
        
        // 새로운 중량이 기존의 최대 중량보다 클경우
        if(weight > ans){
            ans = weight;
        }
    }
    
    cout << ans << "\n";
    
    return 0;
}