5) 백준 2217 - 로프

<문제>

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

2217번: 로프

그리디 문제를 5문제 정도 풀었는데 이기적으로 생각하면 풀기가 쉬워지는 것 같다. (무조건 많이 많이)

 

<코드>

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

using namespace std;

bool comp(int a, int b){
	return a > b;
}

int main(void) {
	vector<int> ropes;
	int N, a;
	cin >> N;
	
	for(int i = 0; i < N; i++){
		cin >> a;
		ropes.push_back(a);
	}
	
	sort(ropes.begin(), ropes.end(), comp);
	
	int Max = 0;
	
	for(int i = 0; i < N; i++) {
		Max = max(Max, ropes[i]*(i+1));
	}
	
	cout << Max;
	
	return 0;	
}

vector에다 최대한 걸 수 있는 중량을 넣어준 후에 내림차순으로 정렬한다.

로프가 여러개 있을 경우 가장 중량을 적게 들 수 있는 로프가 기준이 되는데 내림차순으로 정렬하여 이를 이용할 것이다.

천천히 생각해보자. 가장 중량을 많이들 수 있는 로프는 따로 혼자 써야 그 힘을 제대로 발휘할 수 있다.

예를 들어서 20kg을 들 수 있는 로프와 2kg을 들 수 있는 로프를 동시에 쓴다고 했을 때 이 두 로프를 동시에 쓰면 최대 4kg밖에 들 수 없다. 가장 무게를 조금 들 수 있는 로프가 기준이 되기 때문이다.

때문에 큰 로프부터 하나씩 늘려가며 가장 무게를 조금 들수 있는 로프에 사용한 로프의 개수를 곱해준다. 이 중 가장 큰 값만 골라내면 된다.

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

그리디 조하