백준 2217 로프

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

 

서론

그리디 알고리즘 문제.

 

---

아이디어

예상되는 예제 몇개를 뽑아봤다.

 

1. 입력 : 10, 15 / 출력 : 20

2. 입력 : 10, 15, 20 / 출력 : 30

3. 입력 : 10, 15, 40 / 출력 : 40

4. 입력 : 10, 30, 40 / 출력 : 60

5. 입력 : 10, 20, 30, 40, 50 / 출력 : 90

 

각 예제에서 로프 하나가 버틸 수 있는 최대 하중의 최소인 10*n이 정답이 아님을 볼 수 있다.

예제 5에서 20*n은 안된다. 10의 하중의 줄이 버틸 수 없다.

 

5번 예제는 견딜 수 있는 최대 하중이

10*5 = 50 (10,20,30,40,50 사용)

20*4 = 80 (20,30,40,50 사용)

30*3 = 90 (30,40,50 사용)

40*2 = 80 (40,50 사용)

50*1 = 50 (50 사용)

의 방법들이 나오는데 그중 최대값인 90을 출력하면 된다.

 

---

구현

//c++

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

using namespace std;

int main() {
	vector<int>v;
	vector<int>v2;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		v.push_back(tmp);
	}

	sort(v.begin(), v.end());

	for (int i = n; i > 0; i--) {
		v2.push_back(v[n-i]*i);
	}

	cout << *max_element(v2.begin(), v2.end());
}