[BOJ] 2217 : 로프

Question

---

Solution

• 밧줄의 무게를 vector에 저장하고 내림차순으로 정렬
• i 밧줄의 무게 * (i 밧줄의 무게보다 큰 밧줄 의 수 + 1) 공식을 이용한다

예를들면 [5, 4, 3, 2, 1] 이 있을 때, 5 * 1, 4 * 2, 3 * 3, 2 * 4, 1 * 5 가 되어 최대 무게인 3 * 3 = 9를 찾을 수 있다.

---

Cord

#include <iostream>
#include <algorithm>

using namespace std;

int arr[100000];

// 내림차순 정렬로 재정의
bool compare(int _a, int _b)
{
	return _a > _b;
}

int main()
{
	// 밧줄의 수 입력
	int n;
	cin >> n;

	// 밧줄의 무게를 배열에 저장
	int weight;
	pair<int, int> p;
	for (int i = 0; i < n; i++)
	{
		cin >> weight;
		arr[i] = weight;
	}

	// 내림차순 정렬 실행
	sort(arr, arr + n, compare);
	
	// 최대 무게 구하기
	int max = 0;
	for (int i = 0; i < n; i++)
	{
		if (max < arr[i] * (i + 1))
		{
			max = arr[i] * (i + 1);
		}
	}

	// 출력
	cout << max;

	return 0;
}

---

Result