백준 2217 로프 c++ [컴공과고씨]

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

2217번: 로프

이 문제는 어떤 식으로 접근했냐면 한 로프를 사용한다고 가정했을 때, 자기보다 많은 무게를 드는 로프는 결국 자신의 로프의 최대 들 수 있는 용량을 모두 들 수 있다는 것을 이용했다.

10 30 50 50 85 90 이라는 무게를 들 수 있는 로프가 있을 때 10로프를 이용해서 들 수 있는 최대 중량은? 10과 10보다 큰 로프의 개수를 10에 곱해주면 총 60을 들 수 있다. 30로프를 이용할 때는? 30과 30보다 큰 로프 즉, 30보다 큰 로프의 개수 +1에 자신이 들 수 있는 무게 30을 곱해주면 된다. 이렇게 해서 각 로프를 이용할 때 들 수 있는 최대 용량을 구해서 각각의 값들에서 가장 큰 값이 모든 로프에서 들 수 있는 최대 중량이 된다.

정리하면 A용량의 로프를 이용할 때 들 수 있는 최대 용량은

(A가 들 수 있는 최대 용량)*(A보다 큰 용량의 로프의 개수 + 1) 이 된다.

 

전체코드

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    long long loap[100001];
    int n;
    cin >> n;
    for (int i = 0; i < n;i++){
        cin >> loap[i];
    }
    sort(loap, loap + n); // 오름차순 정렬
    long long most = 0;
    for (int i = 0; i < n;i++){
        if(most < loap[i]*(n-i)){ 
            most = loap[i]*(n-i); // (자기가 들 수 있는 최대 용량)*(자기보다 큰 용량의 로프의 개수 + 자신) 
        }
    }
    cout << most;
    return 0;
}

 

사용알고리즘 : sort

 

yea!