[BOJ] 2217 로프

Link

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

Note

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;
}

2019-06-02 18:25:57에 Tistory에서 작성되었습니다.