[백준/c++] 2217 - 로프

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

2217번: 로프

---

1) 풀이

이 문제가 '그리디 알고리즘'과 관련된 문제라고 하던데.. 사실 난 그런 알고리즘 모른다😂

나중에 시간 날 때 찾아보고 정리해놔야지...(이러고 안 적은게 수십개.. 부지런해지자ㅠ~)

 

이 문제에서 고민해봐야 할 조건은 두 가지

1) 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.

2) k개의 로프를 사용해 중량 w를 들어올리면 각 로프에 w/k의 중량이 걸린다. 

 

가령 여러개의 로프를 사용하는 것보다 하나의 로프가 더 많은 중량을 들 수 있다면 그 하나의 로프가 들 수 있는 최대 중량이 곧 답이 된다는 의미이며  각각의 로프에는 개수만큼 나눠진 동등한 중량이 걸리기 때문에

최대중량이 가장 큰 로프를 사용한다고 하더라도, 다른 로프들이 나눠진 중량을 버틸 수 없다면 사용할 수 없다.

 

이 문제를 최대한 단순하게 생각해보면 최대중량이 가장 큰 로프의 최대중량을 들어올리는 경우부터 생각하면 된다.

(1의 조건으로 로프 하나만 사용해도 된다)

 

1) 모든 로프의 중량을 내림차순으로 sort 한다

2) 내림차순으로 된 중량을 첫번째 중량*1, 두번째 중량*2, 세번째 중량*3...

식으로 늘려가며 로프들이 버틸 수 있는 최대 중량을 구한다. (max 함수 이용)

 

이렇게 하면 답이 나오는데, 2의 설명을 덧붙여야 할 것 같다.

 

예제 입력을 이용하여 설명해보겠다.

만약에 10, 15 의 로프 2개가 있다고 가정하자.

이들을 내림차순으로 정렬해보면 15, 10 의 순서가 된다.

그러면 우리는 15를 들 수 있는 로프 하나만으로 w가 15인 중량을 든다고 생각하자.

그러면, 15*1=15 현재까지는 들 수 있는 최대중량은 15이다.다음으로 10으로 넘어가서 생각해보자. 현재 로프들의 중량은 내림차순으로 정렬되어 있기 때문에만약 우리가 앞서 살펴보았던 로프의 최대중량을 알지 못하더라도 최소 10의 중량은 들 수 있을 것이다.즉, 현재 로프와 앞서 정렬된 로프를 모두 이용하여 들 수 있는  최대 중량은

10*2 = 20 이 될 것이다.

(w/k 의 조건으로 두개의 로프는 동등하게 w/2 의 중량을 들게 될텐데, 현재 로프의 최대 중량이 10이고앞선 로프는 당연히 10의 중량을 수용할 수 있기 때문에 10*2)그렇게 되면 앞서 들 수 있었던 15보다 큰 중량을 들 수 있게 되므로 이 예제에서의 정답은 20이 되는 것이다.

 

로프의 개수가 이보다 더 많더라도 위에서 설명한 방식대로 처리가 가능하다.이해가 안 되면 코드와 함께 살펴보자!

 

2) 최종 소스코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool func(int a, int b) { //내림차순 정렬을 위한 함수
	return a > b;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;
	vector<int>v; //로프 중량 저장하는 벡터
	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		v.push_back(tmp);
	}
	sort(v.begin(), v.end(), func); //내림차순 정렬
	int ans = 0;
	for (int i = 0; i < n; i++) {
		ans = max(ans, v[i] * (i + 1)); //버틸 수 있는 가장 큰 최대중량 구하기
	}
	cout << ans;

}

3) 참고자료