백준 2217 로프 문제 C++

백준 로프 2217 C++

문제설명

문제

N(1 ≤ N ≤ 100,000)개의 로프가 있습니다. 각각의 로프는 들 수 있는 최대 중량이 다릅니다.

k개의 로프를 병렬로 연결하면, 중량 w인 물체를 들 때 각 로프에 걸리는 중량은 w/k가 됩니다.

이때, k개의 로프 중 가장 약한 로프가 버틸 수 있는 중량 이상이어야 합니다.

로프를 몇 개 골라 병렬로 연결했을 때 들 수 있는 최대 중량을 구하십시오.

---

문제 작동원리

• 로프를 하나씩 늘려가며 계산합니다.
• 예를 들어 로프 중 가장 약한 로프가 10이고, 2개를 사용한다면 최대 중량은 $10 \times 2 = 20$ 입니다.
• 만약 로프 중 가장 약한 로프가 5이고, 3개를 사용한다면 최대 중량은 $5 \times 3 = 15$ 인데, 20보다는 작으므로 20이 더 좋은 선택입니다.
• 즉, k개의 로프를 사용했을 때 최대 중량은 $k \times (\text{k번째 로프의 내구력})$ 입니다.
• 모든 k(1부터 N까지)를 확인하며 최대값을 구해야 합니다.

---

테스트케이스

2
10
15

출력:

20

---

전체코드

#include <iostream>
#include <algorithm>
using namespace std;
bool cmp(int a, int b) {
    return a > b; // 내림차순 정렬
}
int main() {
    int N;
    cin >> N;
    int arr[100000];
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
    sort(arr, arr + N, cmp);
    int maxVal = 0;
    for (int i = 0; i < N; i++) {
        int weight = arr[i] * (i + 1);
        if (weight > maxVal)
            maxVal = weight;
    }
    cout << maxVal << "\n";
    return 0;
}

---

아이디어

1. 로프를 내림차순 정렬한다
   로프들이 버틸 수 있는 중량을 큰 순서대로 정렬합니다.
   예를 들어, 입력이 [10, 15, 20, 5] 라면 정렬 후 [20, 15, 10, 5]가 됩니다.
   이렇게 정렬하면, 앞쪽에 강한 로프들이 모이게 되어 계산이 편리해집니다.


2. k개의 로프를 선택했을 때 들 수 있는 최대 중량 계산하기
   k개의 로프를 사용할 때, 그 중 가장 약한 로프의 중량이 병렬로 걸리는 중량의 한계입니다.
   즉, 가장 약한 로프의 버티는 힘 arr[k-1]에 k를 곱해야 실제 들 수 있는 중량이 됩니다.
   예를 들어, 정렬된 배열이 [20, 15, 10, 5] 일 때,
   
   • k=1: $20 \times 1 = 20$ (하나만 사용)
   • k=2: $15 \times 2 = 30$ (두 개 사용, 약한 로프가 15)
   • k=3: $10 \times 3 = 30$
   • k=4: $5 \times 4 = 20$
   이렇게 각 k에 대해 계산한 값을 비교하여 가장 큰 값을 찾습니다.


3. 모든 k에 대해 최대값 갱신하기
   1부터 N까지 모든 k에 대해 계산을 진행하고, 그중 가장 큰 값을 최종 정답으로 정합니다.


4. 최종 답
   위 과정에서 찾은 최대값이 "로프 몇 개를 병렬로 연결했을 때 들 수 있는 최대 중량"이 됩니다.

---

결론

• 로프를 정렬하는 이유는 가장 강한 로프부터 계산해서 최대 중량을 쉽게 찾기 위함입니다.
• k번째 로프를 포함해 k개를 사용한다고 가정하면, 그 중 가장 약한 로프는 k번째 로프입니다.
• 그러므로 arr[k-1] * k 가 해당 경우의 최대 중량입니다.
• 모든 k에 대해 계산 후 최대값을 출력하면 됩니다.