[백준][C++] 2217: 로프

문제

2217번: 로프

풀이

그리디

 

로프들 중에서 무게를 많이 견딜 수 있을 만큼 로프를 골라야 한다. 무게를 많이 버틸 수 있는 로프부터 고르는 것이 최선의 방법이므로, 로프를 내림차순으로 정렬한다. 

 

정렬한 로프를 앞에서부터 탐색한다. i번째 로프에서 최대한 버틸 수 있는 무게는 (i번째로프가 견딜 수 있는 무게) * (i 까지 로프의 수)이다. 이 방법으로 최대 무게를 찾는다. 

 

코드

#include <iostream>
#include <algorithm>

using namespace std;

int nums[100000];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;

    for (int i = 0; i < N; ++i)
    {
        cin >> nums[i];
    }

    // 내림차순 정렬
    sort(nums, nums + N, greater<int>());

    // i번째 로프가 버틸 수 있는 무게는 nums[i] * (현재까지의 로프 수)이다. 
    // 0번째 로프부터 무게를 위의 방법으로 비교하며 최대 무게를 찾는다.
    int answer = 0;
    for (int i = 0; i < N; ++i)
    {
        answer = max(answer, (i + 1) * nums[i]);
    }

    cout << answer;

    return 0;
}