BOJ (C/C++) 2217번: 로프

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

2217번: 로프

---

풀이

- n개의 로프가 들 수 있는 최대 무게는 (가장 적게 들 수 있는 로프의 중량)*(로프의 개수)

- 로프의 최대 중량을 내림차순으로 정렬하고, 다음 로프를 사용했을 때 들 수 있는 중량과 현재 중량을 비교해 최대 중량을 구함

 

- i번 째 로프까지 중량 < i-1번째 로프까지 중량이면 바로 멈춰도 된다고 생각했는데 아래와 같은 반례가 있을 수 있다

 

Rope (정렬 후)	15	11	9	7	6
최대 중량	15	22	27	28	30

---

코드

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

vector <unsigned int> Rope;

bool cmp(unsigned int a, unsigned int b) { return a > b; }
int main() {
	unsigned int N, l, weight;

	// input
	scanf("%u", &N);
	for (int i = 0; i < N; i++) {
		scanf("%u", &l);
		Rope.push_back(l);
	}
	
	// 내림차순 정렬
	sort(Rope.begin(), Rope.end(), cmp);

	// 최대 무게 구하기
	weight = Rope[0];
	for (int i = 1; i < N; i++) {
		// i번 째 로프를 사용하여 들 수 있는 무게와 현재까지 들 수 있는 최대 무게 비교
		weight = weight > Rope[i] * (i + 1) ? weight : Rope[i] * (i + 1);
	}

	printf("%u", weight);
	return 0;
}