[백준 BOJ / C++] 2217번: 로프

문제

 

<문제>

N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런저런 물체를 들어 올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.

 

하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어 올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.

 

각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.

 

<입력>

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

 

<출력>

첫째 줄에 답을 출력한다.

 

www.acmicpc.net/problem/2217

2217번: 로프

 

 

 

 

문제 풀이

 

각 로프가 버틸 수 있는 최대 중량을 내림차순으로 정렬한 뒤 로프를 1개만 이용했을 경우, 2개만 이용했을 경우, ..., N개 이용했을 경우의 최대 중량을 구합니다. 이때 가장 큰 최대 중량이 answer가 됩니다. 

 

예를 들어 정렬한 rope의 최대 중량이 [15, 10, 7, 5, 5]일 경우

• 로프 1개 이용
  weight = 15 * 1 = 15
• 로프 2개 이용
  weight = 10 * 2 = 20
• 로프 3개 이용
  weight = 7 * 3 = 21
• 로프 4개 이용
  weight = 5 * 4 = 20
• 로프 5개 이용
  weight = 5 * 5 = 25

따라서 max_weight은 25가 됩니다. 

 

내림차순 정렬에는 functional 헤더에 정의되어 있는 greater<>()를 이용했습니다. 

 

 

 

소스코드

 

//2217번: 로프 
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
 
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    int N, answer = 0;
    int max_weight = 0;
    cin >> N;
    vector<int> rope(N);
    for(int i = 0; i < N; i++)
        cin >> rope[i];
 
    sort(rope.begin(), rope.end(), greater<>());    //내림차순 정렬
 
    for(int i = 0; i < N; i++) {
        if(rope[i] * (i + 1) > max_weight)
            max_weight = rope[i] * (i + 1);
    }
 
    answer = max_weight;
    cout << answer;
 
    return 0;
}

 

 

 

 

 

 

공부한 것을 정리한 내용입니다. 수정할 부분이 있다면 알려주시면 감사하겠습니다 :)