[C++] 백준 2217번 로프

1. 문제이해

2217번: 로프 (acmicpc.net)

2217번: 로프

 

로프의 개수(N)와 각 로프가 버틸 수 있는 최대 중량이 주어진다.

로프를 이용해 중량이 W인 물체를 들어올리려고 할 때, 각 로프에는 동일한 중량이 걸리게 된다. (N / W)

로프중에서 몇 개만 뽑아서 사용하는 것이 가능할때,

들어올릴 수 있는 물체의 최대중량을 구하는 것이 목표이다.

 

 

 

2. 문제풀이

 

로프를 이용해 들 수 있는 물체의 최대중량을 구하는 문제이다.

언뜻 보면 간단해보이는 문제이지만, 두가지 조건이 있다.

 

1. 로프들 중 몇개만 뽑아서 사용하는 것이 가능하다.

2. 모든 로프에는 동일한 중량이 걸리게 된다.

 

위 두가지 조건을 고려하여 문제를 살펴보면 다음과 같다.

 

<예제 1>

 

문제의 예제에서는 최대중량이 10, 15인 로프 2개가 주어진다.

이를 이용해 물체를 들어올릴 수 있는 경우는 다음과 같다.

 

1. 15인 로프 하나만 사용한다면, 들어올릴 수 있는 최대 중량은 15

2. 10인 로프 하나만 사용한다면, 들어올릴 수 있는 최대 중량은 10

3. 10, 15인 로프를 두개 사용한다면, 들어올릴 수 있는 최대 중량은 10 + 10 = 20

 

따라서, 위 로프들을 이용해 들어올릴 수 있는 최대 중량은 20이다.

3의 경우 20이 나오는 이유는 2. 모든 로프에는 동일한 중량이 걸리게 된다.때문이다.

10, 15 중 더 작은 값은 10이고, 10을 넘은 값을 걸게 되면 최대 중량이 10인 로프는 끊어지게 된다.

따라서, 로프 N개를 사용할 경우에는 로프로 들 수 있는 최대 중량은 (해당 로프들 중 최소중량) x N이 된다.

 

 

<예제 2>

 

다른 예제를 하나 더 살펴보자.

최대 중량이 2, 10, 8, 5, 7 인 로프 5개가 주어졌을 경우이다.

중량이 큰 로프부터 꺼내어 보아야하기 때문에, 위 값들을 정렬하면 2, 5, 7, 8, 10 이 된다.

위 로프들 중 큰 값부터 차례대로 사용해 들어올리면, 들어올릴 수 있는 경우는 다음과 같다.

 

1. 10인 로프 하나만 사용한다면, 들어올릴 수 있는 최대 중량은 10 (10 x 1)

2. 10, 8인 로프를 두개 사용한다면, 들어올릴 수 있는 최대 중량은 8 + 8 = 16 (8 x 2)

3. 10, 8, 7인 로프를 세개 사용한다면, 들어올릴 수 있는 최대 중량은 7 + 7 + 7 = 21 (7 x 3)

4. 10, 8, 7, 5인 로프를 네개 사용한다면, 들어올릴 수 있는 최대 중량은 5 + 5 + 5 + 5 = 20 (5 x 4)

5. 10, 8, 7, 5, 2 인 로프를 다섯개 사용한다면,들어올릴 수 있는 최대 중량은 2 + 2 + 2 + 2 + 2 = 10 (2 x 5)

 

따라서, 위 로프들을 이용해 들어올릴 수 있는 최대 중량은 21이다.

중량이 큰 로프부터 꺼내어 보는 이유는 1. 로프들 중 몇개만 뽑아서 사용하는 것이 가능하다.때문이다.

중량이 큰 로프를 가지고 뽑아야, 들어올릴 수 있는 물체의 최대 중량이 더 커지게 된다.

(10, 2 두개의 로프로 최대 4인 물체를 드는 것과, 10, 8 두개의 로프로 최대 16인 물체를 드는 것의 차이)

 

따라서, 로프가 N개 주어졌을 때,

위와 같은 조건을 고려하여 들어올릴 수 있는 물체의 최대 중량을 구하는 방법은 다음과 같다.

 

1. 주어진 로프의 최대중량을 정렬

2. 로프의 중량이 큰 것부터 뽑아나가며 해당 경우의 값을 최댓값과 비교

 

 

 

3. 소스코드

#include <iostream>
#include <algorithm>
using namespace std;
int rope[100000];

int main() {
	int N;	// 로프의 개수
	int current;	// 현재 중량
	int max;	// 최대 중량
	cin >> N;

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

	// 로프의 중량을 정렬
	sort(rope, rope + N);
	
	// 최댓값을 우선 중량이 가장 큰 로프 하나만 이용했을 때로 초기화
	max = rope[N - 1];

	for (int i = N - 1; i >= 0; i--) {
		// 현재 로프의 중량 (해당 로프의 중량 * 몇 개 달았는지)
		current = rope[i] * (N - i);
		if (max < current) {	// 최대 중량보다 현재 중량이 더 크다면
			max = current;	// 최대 중량을 현재 값으로 초기화
		}
	}

	cout << max;

	return 0;
}

2. 문제풀이 방법에서 도출해낸 그대로 코드를 구현했다.

로프의 개수와 각 로프의 중량을 입력받아 정렬한 후, 로프의 중량이 큰것부터 차례로 뽑아

해당 경우 들어올릴 수 있는 중량(current)과, 현재까지 들어올릴 수 있는 최대 중량(max)을 비교,

현재 들어올릴 수 있는 중량이 더 크다면 최대 중량을 초기화했다.

 

 

---

내가 이해하는데 오래걸린 문제라.. 오늘은 문제풀이 부분을 자세하게 써보았다.

내가 헷갈려했던 부분이나 이해가 잘 되지 않았던 부분을 자세하게 써보았는데,

혹여나 헤매고 계실 분들에게 많은 도움이 되었으면 좋겠다. 😊