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

문제

 

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

2217번: 로프

 

설명

 

처음엔 이 문제가 이해가 잘 안갔다.

설명해보자면

만약에 18짜리 중량인 물체가 있다면 버틸수 있는 최대 중량이 6인 로프 3개로 물체를 들 수 있다.

반대로 위에서 말한 6짜리 로프 3개로는 로프 1~3개를 이용하여 6, 12, 18 짜리 중량인 물체를 들수 있는데 그 중에 최대 중량은 18이기 떄문에

답은 18이 된다.

 

로직을 생각해보면 만약에 버틸 수 있는 최대중량이 1,5,10 인 로프 3개가 있다고 가정하면

모든 로프를 사용하지 않고 임의로 몇 개의 로프를 골라서 사용해도 된다고 했으니

1) 3개를 사용하는 경우

2) 2개를 사용하는 경우

3) 1개를 사용하는 경우

이렇게 3가지 경우로 나눌 수 있다.

 

1)번 경우로는 1,5,10 로프로는 최대 3짜리 중량인 물체를 들 수 있다.

2)번 경우로는 5,10 로프를 이용하여 최대 10 짜리 중량인 물체를 들 수 있다.

또 1,10 로프를 이용하여 최대 2 짜리 중량인 물체를 들 수 있다.

또 1,5 로프를 이용하여 최대 2 짜리 중량인 물체를 들 수 있다.

3)번 경우로는 1 로프 하나를 이용하여 1 짜리 중량인 물체를 들 수 있다.

또 5 로프 하나를 이용하여 5 짜리 중량인 물체를 들 수 있다.

또 10로프 하나를 이용하여 10 짜리 중량인 물체를 들 수 있다.

 

결론으로 최대 10 짜리 중량인 물체를 들 수 있다

2)번의 경우로는 10, 2, 2 세가지 경우의 수가 나오는데 굳이 3가지 경우의 수를 모두 검토할 필요가 없이

버틸수있는 중량이 큰 로프 2개를 선택하면 된다!!

 

따라서 정렬하고 정렬된 원소들을 i개씩 비교해나가면서 최댓값을 찾는다. 

 

 

코드

#include<iostream>
#include<algorithm>
using namespace std;

int a[100000];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a + n);

	int result = 0;
	for (int i = 1; i <= n; i++) {
		result = max(result, a[n - i] * i);
	}
	cout << result;

	return 0;
}

 

생각보다 간단하게 구현할수있는 문제였다.