[BOJ] 로프 2217번 C++

 

문제

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

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

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

입력

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

출력

첫째 줄에 답을 출력한다.

 

접근 방식

 

로프가 버틸 수 있는 최대 중량을 구하기 위해 그리디로 간단하게 구할 수 있다.

먼저 로프가 버틸 수 있는 최대 중량을 정렬해준다.

그 후 반복문을 통해 정렬된 배열을 끝에서 시작으로 순회하면서 최대 중량의 값이  현재 값 * 인덱스보다 큰지 확인하면 된다

즉, 만약 10 15로 정렬된 배열이 있다면

먼저 15 * 1 = 15가 되고

10 * 2 vs 15를 비교하면 20이 더 크므로

정답은 20이다.

 

코드

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

int main() {
    int N; cin>>N;
    vector<int> v(N+1);
    for(int i=0; i<N; i++) cin>>v[i];

    sort(v.begin(), v.begin()+N);

    int ans=0;

    for(int i=1; i<=N; i++) {
        ans = max(ans, v[N-i]*i);
    }
    cout<<ans;

}