[BOJ] 2217번 로프

풀이

이 문제의 경우 모든 경우의 수를 계산해주는 것을 목표로 하였습니다.
로프의 최대 중량을 구하기 위해서는

1.모든(n개)로프를 사용하는 경우
2. n-1개의 로프를 사용하는 경우
3. n-2개의 로프를 사용하는 경우
...
n. 1개의 로프를 사용하는 경우

이렇게 나눠지게 됩니다.
이 중 최대값이 우리가 찾고자 하는 결과값입니다.
위의 경우를 구현하기 위해서 vector를 이용하여 값을 정렬하고 하나씩 pop 해주는 과정을 이용하여 최대값을 찾아 주었습니다.

코드

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

using namespace std;

void init() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
}

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

int main() {
	init();

	int n;
	cin >> n;

	// 벡터에 로프의 최대 중량들을 저장해준다.
	vector<int> v;
	for (int i = 0; i < n; i++) {
		int temp;
		cin >> temp;
		v.push_back(temp);
	}

	// 내림차순으로 정렬되어 있다.
	// vector의 back 부분에 제일 작은 숫자가 위치해 있는 상태
	sort(v.begin(), v.end(), cmp);
	
	int max = 0;

	for (int i = 0; i < n; i++) {
		int t = v.back() * v.size();
		if (t > max) {
			max = t;
		}

		v.pop_back();
	}

	cout << max;

	return 0;
}

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