백준 2217 - 로프

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

2217번: 로프

문제 설명

---

로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다르다.

하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다.

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

각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오.

(단, 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.)

 

 

접근 방식

---

하나씩 비교해보는 방식을 사용하면 쉽게 해결할 수 있습니다. 그 전에 예시를 한번 들어보도록 하겠습니다. 

먼저 로프의 개수가 3개가 있으며, 각각은 1,2,3만큼의 중량을 들어올릴수 있다고 가정하면 다음과 같은 메커니즘을 발견할 수 있습니다.

 

1. 여러개의 밧줄을 통해서 들어올릴 때, 반드시 (총무게/밧줄의 개수)는 밧줄이 들수있는 최소의 중량을 초과하면 안된다.

2. 이와 같은 방식으로 Sorting을 진행하고 처음부터 마지막 밧줄까지 1,2,3...,n개

3. 2와 비슷하게 두번째부터 2,3,4,5,....,n 그리고 마지막 n개 하나 까지 비교를 한다.

 

 

코드

---

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

using namespace std;
int n;
bool compare(int a,int b){
    return a>b;
}
int main(){
    cin>>n;
    vector<int>ans;
    vector<int>rope;
    for(int i=0;i<n;i++){
        int temp;cin>>temp;
        rope.push_back(temp);
    }
    sort(rope.begin(),rope.end());
    for(int i=0;i<n;i++){
        ans.push_back(rope[i]*(n-i));
    
    }
    sort(ans.begin(),ans.end(),compare);
    cout<<ans[0]<<"\n";
    return 0;
}

 

funny algorithms *0*~