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

문제

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

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

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

입력

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

출력

첫째 줄에 답을 출력한다.

Solved.ac 레벨

실버 IV

풀이

#include <bits/stdc++.h>

using namespace std;

int n; //로프의 개수
int maxWeight = 1; //최대값을 찾기 위함
vector<int> rope(n);

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;

    for(int i = 0; i < n; i++){
        int wei; //로프 별 하중
        cin >> wei;
        rope.push_back(wei);
    }
    
    sort(rope.begin(), rope.end(), greater<int>()); //로프 길이를 내림차순으로 정렬

    for(int i = 0; i < n; i++){
        if(maxWeight < rope[i] * (i+1))
            maxWeight = rope[i] * (i+1);
    }

    cout << maxWeight << '\n';

    return 0;
}

최근에 DFS와 BFS 즉, 그래프 탐색 알고리즘 공부를 하다가 다른 것도 해야겠다 싶어서 그리디로 넘어왔다.

이 문제의 경우 로프들이 견딜 수 있는 최대 하중을 내림 차순으로 정렬하여 로프가 1개일때부터 n개일때까지 값을 계산해보고, 그 중 가장 큰 값을 낼 수 있었다. 

 

다음과 같이 5개의 로프가 주어졌다고 가정해보자.

 

[ 10, 20, 60, 15, 65] -> [65, 60, 20, 15, 10]

 

이를 내림차순으로 정렬하면 위와 같다.

 

N개의 로프 중 K개의 로프를 골라서 무게가 W인 물체를 들어올릴 때, 들어올릴 수 있는 무게 W의 최대값은

K개의 로프 중 가장 견딜 수 있는 하중이 적은 로프 * K = W의 최대값

왜냐하면 예제의 10, 15의 경우 K=2일때를 보면 2개의 로프가 같은 하중을 양분해서 들어올려야 하나 견딜 수 있는 하중이 10인 로프는 최대 10 까지밖에 견딜 수 없기 때문이다.

1 : 1

...

10 : 10 -> 즉 10 : 10까지만 양분이 가능하므로 20이 들어올릴 수 있는 물체의 무게 W의 최대값이다.

11 : 11 -> 여기서부터는 안된다.

 

따라서 내가 제시한 예제에서 최적해를 구하는 과정을 표로 나타내면 다음과 같이 볼 수 있다.

로프가 견딜 수 있는 하중	k (골라낸 줄의 개수)	k개의 줄로 견딜 수 있는 하중
65	1	65
60	2	120
20	3	60
15	4	60
10	5	50

즉 K = 2일때 W가 최대가 된다는 것을 알 수가 있다.

 

---

그리디 알고리즘은 처음 풀어보는 것은 아니지만 매 문제마다 낯설다.

그래프 탐색 알고리즘은 문제의 조건에 맞춰 구현하고 스택, 재귀, 큐 등 공식만 대입하면 무조건 해결이 되는 알고리즘이었다면

그리디는 어떻게 하면 주어진 환경에서 최적 조건이 나오고 어떤 것들을 따져봐야 할지 나 스스로가 모두 생각하고 결정하고 구현해야 한다는 것에 있어서 그 어려움이 있다.

 

많이 해보는 것 이외에는 답이 없지 않을까 싶다.

 

2217번: 로프