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

문제

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

백준 2217

 

문제 내용

입력으로 각각의 로프가 들 수 있는 최대 중량이 주어진다.

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

로프가 여러 개 있고, 로프를 사용하여 물체를 들어올릴 수 있는 최대 중량을 구하는 문제이다.

 

문제 풀이

병렬로 들어올릴 수 있는 상황을 생각해보자.

예제 1에서는 각각의 로프가 10과 15의 중량을 버틸 수 있는 것으로 주어졌다.

두 로프를 병렬로 연결하여 30짜리 물건을 들 수 있을까?

30/2=15로 각각의 로프에 15의 중량이 걸리기 때문에 최대 중량이 10인 로프는 끊어지게 될 것이다.

 

따라서, 로프가 버틸 수 있는 중량의 기준을 가장 작은 로프로 해야 한다.

w = (주어진 로프들 중에 최소 중량) * 병렬 연결된 로프의 수

 

로프의 개수가 3개 이상 들어올 경우를 살펴보자

[3, 6, 8, 9] 와 같이 로프의 최대 중량이 주어졌다고 하자. (정렬은 보기 쉽게 임의로 해두었다.)

1) 3, 6, 8, 9 를 모두 병렬 연결 =>  3*4=12
2) 6, 8, 9 를 병렬 연결 =>  6*3=18
3) 8,9 를 병렬 연결 =>  8*2=16
4) 9 를 병렬 연결 =>  9*1=9

위 경우를 보았을 때 2번(6,8,9를 병렬 연결)의 경우가 제일 중량을 많이 버틸 수 있다.

 

코드

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> arr(n, 0);

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

    sort(arr.begin(), arr.end()); // 오름차순으로 정렬

    for (int i = 0; i < n; i++) {
        arr[i] *= (n - i); // 병렬 연결을 위한 계산
    }
    cout << *max_element(arr.begin(), arr.end()); // 병렬 연결을 했을 때의 최대값
}

 

문제 코드 설명

algorithm 헤더의 sort와 max_element를 사용하면 쉽게 해결할 수 있다.

+) max_element는 범위 안에 있는 최대값의 "주소"를 반환한다. 따라서 최대값을 얻고 싶다면 앞에 * 를 붙여야 한다.