[백준 2217] 로프

그리디 문제

www.acmicpc.net/problem/2217

---

[문제 풀이]

 

N개의 로프를 사용하여 들 수 있는 최대의 중량을 구하는 문제입니다.

 

N개의 로프를 사용하여 들 수 있는 중량의 모든 경우의 수를 구한다면 $O(N^2)$이 걸리게 됩니다.

N의 최대 제한이 100,000이므로 당연히 시간 초과가 발생합니다.

 

그러므로 단순하게 전부 구하는 방식 말고 다른 방식을 찾아야 합니다.

 

 

이 문제를 어떻게 접근하는지 잘 생각해봅시다.

 

우리가 구해야 하는 것은 로프가 버틸 수 있는 최대 중량입니다.

사용할 수 있다면 튼튼한 로프를 사용하는 것이 좋아 보입니다.

또한 상대적으로 튼튼하지 않은 로프를 버리고 튼튼한 로프만 사용하여 물체를 들어 올리는 것도 좋아 보입니다.

 

튼튼하지 않은 로프를 버리는 과정에서, 버린다면 가장 약한 로프를 버리는 것이 바람직하다는 것은 당연히 떠올릴 수 있을 겁니다.

로프를 한 개를 버린다고 생각했을 때, 가장 약한 로프를 버리지 않고 다른 로프를 버리는 것은 오히려 들 수 있는 중량을 낮추는 행동이기 때문입니다.

 

예시를 들어서 중량 제한이 1, 5, 8, 10인 로프가 있다고 가정하겠습니다.

4개의 로프를 사용하여 들 수 있는 중량은 겨우 4에 불과합니다. (가장 작은 제한이 1이고 4개의 로프로 들 수 있으므로 1 * 4 = 4)

여기서 제한이 1인 로프를 버린다면, 15나 되는 중량을 들 수 있을 겁니다. (가장 작은 제한이 5이고 3개의 로프로 들 수 있으므로 5 * 3 = 15)

 

즉, N개의 로프를 전부 쓰다가 가장 약한 로프를 하나씩 버려가면서 무게를 체크하기만 해도 들어 올릴 수 있는 최대 중량을 구할 수 있습니다.

그리디 알고리즘을 사용하여 불필요한 연산 횟수를 없애버린 것입니다.

 

위와 같이 가장 중량 제한이 낮은 로프를 버리면서 들 수 있는 무게를 체크하기만 한다면 $O(N^2)$이던 시간 복잡도가 무려 $O(N)$으로 줄어들게 되고 문제를 해결할 수 있게 됩니다.

 

---

[소스 코드] / C++

 

 

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

using namespace std;

int Max(int a, int b) {
	return a <= b ? b : a;
}

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

	int N;
	cin >> N;

	vector<int> rope(N);

	for (int i = 0; i < N; i++) {
		int n;
		cin >> n;
		rope[i] = n;
	}

	sort(rope.begin(), rope.end(), greater<int>());

	int result = rope[0];
	for (int i = 1; i < N; i++) {
		int cur = (i + 1) * rope[i];
		result = Max(result, cur);
	}

	cout << result;

	return 0;
}