[BOJ] 백준 2217 로프

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


 이 문제는, 로프의 개수가 주어지고 각각의 로프가 견딜 수 있는 하중이 주어졌을 때
해당 로프들을 병렬로 연결 하였을 때 버틸 수 있는 최대 하중을 구하는 문제 입니다.

그리디 알고리즘을 사용한 이유는, 매 순간 최대 하중을 버틸 수 있는 로프(들)를 선택해야 가장 큰 하중을 버틸 수 있기 때문입니다.

알고리즘은 다음과 같습니다.
1. 로프의 정보를 입력 받은 후 비오름차순으로 정렬합니다.
2. 해당 상황에서 가장 큰 하중을 견딜 수 있는 로프를 선택합니다.
3. 그 로프를 선택하고 병렬로 연결하였을때 버틸 수 있는 최대 하중을 봅니다.
3-1. 이때, 최대하중을 계산하기 위해서 이 로프를 계산에 포함했을 때 몇까지 버틸 수있나 보는 것 입니다.


소스코드 :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std;   bool desc(int a, int b) {     return a > b; }   int main() {     ios_base::sync_with_stdio(false);     cin.tie(0);     int n;     cin >> n;     vector<int> v(n);     for (int i = 0; i < n; i++) {         cin >> v[i];     }     // alignment     sort(v.begin(), v.end(), desc);     long long maximum = 0ll;     for (int i = 0; i < n; i++) {         if (maximum < v[i] * (i + 1)) {             maximum = v[i] * (i + 1);         }     }     cout << maximum << endl; }   Colored by Color Scripter

cs