백준 2217 _ 로프

www.acmicpc.net/problem/2217

2217번: 로프

---

✨ 내 소스 코드

#include<iostream>
#include <algorithm>
using namespace std;
bool desc(int a, int b) {
	return a > b;
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
    
	int N,max_n=0;
	int rope[100000];

	cin >> N;
	
	for (int i = 0; i < N;i++) {
		cin >> rope[i];
	}
	sort(rope,rope+N, desc);

	for (int i = 0; i < N; i++) {
		int result = rope[i] * (i + 1);
		max_n = max(result, max_n);
	}

	cout << max_n;

	return 0;
}

 

🙏 문제 해설

2217번은 문제를 봤을 때, 처음에 잘 이해가 되지 않았다

 

백준 풀이에 의하면

'k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다'

라고 했을 때, 10과 15의 로프가 주어지면 최대 중량은 20이 된다고 한다

 

이는 만약에 30 중량의 물체가 주어지면 10과 15 로프에 각각 15, 15씩 중량이 걸리게 되는데

15로프는 15의 중량을 견딜 수 있지만, 10은 15의 중량을 받으면 견딜 수 없게 된다

 

따라서, 연결할 로프의 개수는 2개이고 로프들 중 가장 작은 값인 10이기 때문에

최대 중량은 10 * 2 인 20이 되게 된다

이를 바탕으로 min(rope) * k가 최대 중량이 될 것임을 짐작할 수 있었다

 

 

 

🌱 최대 중량 구하기

sort(rope,rope+N, desc);

 

우선 'algorithm' 라이브러리의 sort 함수를 이용하여 로프를 내림차순으로 정렬해주었다

그러면 가장 중량이 큰 로프부터 중량이 작은 로프 순으로 정렬이 되게 되는데

 

for (int i = 0; i < N; i++) {
	int result = rope[i] * (i + 1);
	max_n = max(result, max_n);
}

 

다음과 같이 현재 로프의 중량과 현재 연결된 로프의 개수를 곱해준 다음에 해당 최대 중량이 max인지 비교하여 답을 구해주면 간단하게 풀리는 문제였다

 

예를 들어,

[15, 30, 10, 20, 25] 라는 로프가 주어진다고 가정해보자

이를 정렬하면 [30, 25, 20, 15, 10]의 순으로 바뀌게 된다

 

30 * 1 = 30으로 최대 중량은 30이 된다

25 * 2 = 50으로 최대 중량은 50이 된다

20 * 3 = 60으로 최대 중량은 60이 된다

15 * 4 = 60으로 최대 중량은 그대로 60이 된다

10 * 5 = 50으로, 이전 최대 중량보다 작기 때문에 최대 중량은 그대로 60이 된다

 

 

 

⭐ 문제 풀이 결과