[백준 2217번] 로프 (C++)

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

2217번: 로프

---

로프 문제는 그리디 알고리즘을 이용하여 해결할 수 있습니다.

 

먼저, 버틸 수 있는 최대 중량이 가장 높은 로프부터 골라야 높은 중량의 물체를 들 수 있습니다. 

따라서, 최대 중량을 기준으로 정렬을 수행해야합니다.

n번째부터 i번째까지 로프를 선택했을 때, 들 수 있는 최대 중량은 S_i * (n - i)입니다. (단, S_i는 i번째 로프의 최대 중량)

왜냐하면 i번째 로프의 최대 중량이 가장 낮기 때문에 n번째부터 i번째 로프까지 i번째 로프의 최대 중량이 걸렸을 때 가장 무거운 물체를 들 수 있기 때문입니다. 

 

아래는 전체 코드입니다.

 

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

int rope[100010];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;

    for(int i = 0; i < n; i++) cin >> rope[i];  // 로프의 최대 중량 입력 받음
    sort(rope, rope + n);   // 최대 중량을 기준으로 정렬 수행
    int m = INT_MIN;

    for(int i = n - 1; i >= 0; i--){
        // 최대 중량이 높은 로프부터 k개의 로프를 선택했을 때
        // 들 수 있는 물체의 최대 중량이 가장 높은 것을 기록 

        int k = n - i;  // 선택한 로프의 개수
        m = max(m, k * rope[i]);    
    }
    cout << m << "\n";
}