[BOJ / C++] 로프 (그리디)

문제링크: https://www.acmicpc.net/problem/2217

 

1. 코드

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

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

    int n;
    cin >> n;

    vector<int> rope(n);
    for (int i = 0; i < n; i++) {
        cin >> rope[i];
    }
    sort(rope.begin(), rope.end(), [](int a, int b) {return a > b;});

    int weight = 0;
    for (int i = 0; i < n; i++) {
        weight = max(weight, rope[i] * (i+1));
    }
    cout << weight;
}

 

 

2. 분석

사용할 로프의 개수를 정하는 것이 핵심이다. 사용할 로프의 개수를 정했다면 중량이 큰 로프부터 그 갯수만큼 선택할 거기 때문이다. 그러면 그리디로 풀이가 가능하다. 따라서 입력을 받고 내림차순으로 정렬한 후에 weight = max(weight, rope[i] * (i+10)); 로 계산한다.

 

3. 시간복잡도

sort에 가장 많은 시간복잡도가 걸린다. O(nlgn)이고, n = 10^5 이므로 nlgn = 10^6 < 10^8으로 시간제한 1초 내에 통과 가능하다.