Baekjoon 2217 로프

Link https://www.acmicpc.net/problem/2217

소스결과 3276 KB / 16 ms

언어 C++ 17

출처 Baekjoon

분류 그리디 알고리즘

 

설명

k개의 로프 정보가 주어질 때, 로프를 사용하여 들어 올릴 수 있는 최대 중량을 계산하여라.

 

알고리즘에 있어 크게 생각할 부분은 없었다.

각 로프 입장에서는 자기가 들 수 있는 값보다 큰 값을 들어올리지는 못하기 때문에 자기 자신을 기준으로 자기보다 많이 들어 올릴 수 있는 수 만큼을 곱해주면 그 로프를 이용 했을 때의 최대 중량이 된다.

최대 값만 찾으면 되기에 배열을 이용해도 되지만 이번 문제에서는 힙을 이용했다.

힙은 최대 힙으로 사용하고, 정렬된 값을 넣을 때에는, (자신의 장력) * (남은 로프의  수)의 값으로 넣어준다.

 

알고리즘

1. 로프의 정보를 입력 받아 오름차순으로 정렬한다.

2. 힙에 로프 정보 * ( 로프의 총 개수 - 탐색하는 인덱스 ) 를 넣는다.

3. 최대 값을 뽑아 출력한다.

 

소스코드

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

using namespace std;

vector<int> ropes;

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

	int n;
	cin >> n;

	ropes.resize(n);

	for (int i = 0; i < n; i++)
		cin >> ropes[i];

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

	priority_queue<int> heap;

	for (int i = 0; i < n; i++)
		heap.push(ropes[i] * (n - i));

	cout << heap.top();

	return 0;
}