[C++] 백준 2217번 로프

 

1) 문제설명

 

백준 Online Judge 2217번 로프

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

2217번: 로프

 

2) 아이디어

문제에 대해서 잘 이해하기만 하면 쉽게 풀 수 있는 과제이다.

로프가 견딜 수 있는 무게가 10, 20 인 경우 각각 10, 10을 들면 되므로 최대 중량은 20이 된다.

다른 예로 로프가 견딜 수 있는 무게가 10, 20, 30 인 경우 10의 무게로 3개의 로프가 전부 다 견딘 다면 최대 중량은 30이 된다. 하지만 전부다 사용할 필요 없이 20, 30의 로프만 사용하여 20, 20 을 견딜 경우 최대중량이 40이 되므로 3개의 로프를 사용하는 것 보다 20, 30 의 로프를 사용하는 것이 더 효율적이다.

 

그러므로 로프가 견딜 수 있는 무게(arr [x])를 오름차순으로 정렬하여 arr [0] * n , arr [1] * (n-1),... , arr [n-1] * 1까지 중에 가장 큰 값을 찾으면 된다.(n은 로프의 개수)

 

3) 코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;

int arr[1000001];
int main() {
	int n;
	cin >> n;
	int* arr = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	sort(arr, arr + n); // 오름차순정렬
	int maxt = arr[0] * n;
	for (int i = 0; i < n; i++) {
		maxt = max(maxt, arr[i] * (n - i));
	}
	cout << maxt << endl;

}