[BOJ/C++] 로프(2217번)

1. 개요

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

2217번: 로프

1-1. 설명

N개 로프가 있다. 이 로프를 이용해 물체를 들어올릴 수 잇다. 각각의 로프는 굵기나 길이가 다르므로 물체의 중량이 서로 다를 수 있다. 하지만 여러개 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개 로프를 이용해 중량이 w인 물체를 들어올릴 때, 각각 로프에는 모두 고르게 w/k만큼 중량이 걸리게 된다. 각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용해 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성한다. 모든 로프를 사용할 필요가 없으며, 임의로 몇개 로프를 골라서 사용해도 된다. 

1-2. 제한 사항

 - 첫 줄에 정수 N이 주어지며 N은 1 이상 100,000 이하

 - 다음 N개 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어지며, 이 값은 10,000을 넘지 않는 자연수

---

2. 구현

2-1. 풀이

문제를 이해하는데 어려움을 느꼈었다, 문제에 대한 조건을 잘 보고 생각해내면 구현 자체는 어렵지 않았다. 설명을 잘 읽어보면 k개의 로프를 이용해 중량이 w인 물체를 올릴 때, 각 로프는 동일하게 w/k만큼 걸리게 된다고 한다. 문제 예제를 한번 살펴보자. 1개의 로프를 이용하면 아래와 같이 나온다

 - 최대 중량 10인 로프 1개 -> 10

 - 최대 중량 15인 로프 1개 -> 15

그럼 2개의 로프를 이용하면 어떻게 되는가? 아래와 같이 나오게 된다.

 - 최대 중량 10, 15인 로프 2개 -> 10 + 10 = 20

여기서 그럼 수식을 하나 유추해낼 수 있다. K개의 로프를 사용할 때 로프가 들 수 있는 최대 중량은 (주어진 로프 중량의 최솟값 * K)이다. 여기서 로프는 큰 용량부터 작은 용량으로 정렬해주고 수식을 사용해야 함을 알게 된다.

 

이제 문제 예제 대신 다른 예제를 들어보자. 우리는 [5, 10, 17, 4]인 로프가 주어졌다고 가정한다. 우선 정렬하면 [17, 10, 5, 4]가 된다. 정의한 수식대로 식을 나열해보면 아래와 같다. 

 - 최대 중량 17인 로프 1개 -> 17 * 1 = 17

 - 최대 중량 17, 10인 로프 2개 -> 10 * 2 = 20

 - 최대 중량 17, 10, 5인 로프 3개 -> 5 * 3 = 15

 - 최대 중량 17, 10, 5, 4인 로프 4개 -> 4 *4 = 16

최대 중량은 그럼 20으로 나오게 된다. 이 방식을 이용해 코드를 구현하면 정답이 나온다. 구현 자체는 금방 끝났으나, 문제를 이해하고 풀이를 도출하기까지 약간의 시간이 걸렸다. 

2-2. 코드

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

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, num;
    vector<int> weights;
    cin >> N;

    for (int i = 0; i < N; i++) {
        cin >> num;
        weights.push_back(num);
    }

    sort(weights.begin(), weights.end(), greater<int>());

    int maxNum = 0; // 최대 용량
    for (int i = 0; i < N; i++) {
        int curNum = weights[i] * (i + 1); 
        if (curNum >= maxNum) maxNum = curNum;
    }
    cout << maxNum;
    return 0;
}