[BOJ 2217] 로프

2217번: 로프

문제 분석

• 중량은 무조건 균등하게 배분된다.
• 작은 로프가 들 수 있는 중량은 그 로프보다 큰 로프는 그 중량은 무조건 들 수 있다.
• 하나의 가장 큰 로프 하나가 드는 중량이 나머지 로프랑 나눠드는 것 보다 클 수 있다.

풀이 방식

• 로프 마다 들 수 있는 중량이 입력되면 이를 오름차순으로 정렬한다.
• 가장 작은 로프부터 (해당 로프의 최대중량 * 해당 로프 이상의 로프의 수)를 구한다.
• 이 중 가장 큰값을 출력한다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> ropes;

int n, w;
int Max;

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

    cin >> n;
    while (n--) {
        cin >> w;
        ropes.push_back(w);
    }
    sort(ropes.begin(), ropes.end());
    for (int i = 0; i < ropes.size(); i++) {
        if (Max < ropes[i] * (ropes.size() - i))
            Max = ropes[i] * (ropes.size() - i);
    }
    cout << Max;
}

느낀 점 

• 이 문제는 문제를 보고 얼마 지나지 않아 문제를 해결하는 방법이 생각 나 금방 해결할 수 있었다. (뿌-듯)

시간 복잡도

• 입력 -> O(n)
• 정렬 -> O(nlogn) 기대
• 최댓값 -> O(n)
  ➣ O(nlogn)