[C++] 백준 2217 : 로프

백준 2217 : 로프

 

문제 링크

www.acmicpc.net/problem/2217

2217번: 로프

 

 

문제 내용

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

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

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

 

 

Idea

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

만약, 어떠한 로프가 w/k보다 들 수 있는 중량이 낮으면 물건을 들어 올릴 수가 없기 때문에, 모든 로프는 최소 w/k보다 커야한다.

따라서 k개의 로프로 들어 올릴 수 있는 최대 중량은 (k개의 로프 중 최대 중량이 낮은 로프) * k이다.

 

단, 로프는 모두 사용할 필요가 없다. 그러므로 요소들을 내림차순으로 정렬한 후 최댓값을 찾는다. 첫 번째 요소부터 차례로 검 사하다 보면 결국 현재 가리키는 인덱스가 현재의 최솟값임을 알 수 있다. 이를 이용하여 코딩하면 쉽게 결과를 도출할 수 있을 것이다.

 

사실 c언어로 하려고 했다가 정렬하는게 귀찮아서 c++로 했다...

 

 

Code

#include <stdio.h>
#include <algorithm>
#define MAX(a,b) a>b?a:b
using namespace std;
 
int arr[100000];
 
//내림차순
bool desc(int a, int b) {
    return a > b;
}
 
int main() {
    int N;
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++)
        scanf("%d", &arr[i]);
 
    //내림차순으로 정렬
    sort(arr, arr + N, desc);
 
    //최대 중량 구하기
    int max = 0;
    for (int i = 0; i < N; i++) {
        int tmp = arr[i] * (i + 1);
        max = MAX(max, tmp);
    }
 
    //결과값 출력
    printf("%d\n", max);
    return 0;
}