2217)로프

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

각 로프마다 견딜 수 있는 최대 무게가 다르다.

n 개의 로프가 무게가 w인 물체를 견딜 때, 각 로프에는 w/n만큼의 무게가 가해진다.

이때 로프들이 견딜 수 있는 최대 무게는 얼마일까?

모든 로프들을 사용한다면, 견딜 수 있는 무게가 가장 적은 로프에 맞춰져야 한다.

예를들어 각 로프들이 견딜 수 있는 무게가 A:10, B:15, C:20, D:30, E:40 이라고 하자.

모든 로프를 사용한다면 w/5를 가장 작은 무게를 견디는 A가 견뎌낼 수 있어야 한다.

만약 w가 60이라면 A에 12만큼의 무게가 가해져 이를 견딜 수 없다.

즉 w의 최대값은 A가 견딜 수 있는 무게인 10에서 5를 곱한 값이다.

여기서 Wmin= Wmax / n 를 얻을 수 있고 (Wmin : 로프가 견딜 수 있는 가장 무게중 최소값, Wmax : 물체의 최대 무게 )

Wmax = Wmin*n로 바꿔서 쓸 수 있다.

문제의 중요한 조건은 모든 로프를 다 사용할 필요가 없다는 것이다.

A:10, B:15, C:20, D:30, E:40에서 몇 개의 로프만 사용해서 그 로프들로 견딜 수 있는 최대 무게를 구해보자.

5개를 사용하면 최대 무게는 10에 맞춰져야 한다. 그래서 w는 50이다.

4개를 사용하면 최대 무게는 15에 맞춰져야 한다. w는 60이다.

3개를 사용하면 최대 무게는 20에 맞춰져야 한다. w는 60이다.

2개를 사용하면 최대 무게는 30에 맞춰져야 한다. w는 60이다.

1개를 사용하면 최대 무게는 40에 맞춰져야 한다. w는 40이다.

결국 로프들이 견딜 수 있는 최대 무게를 구하기 위해 로프들이 견딜 수 있는 무게를 오름차순 정렬하고

(로프가 견딜 수 있는 무게중 i번째로 작은 것) * (i+1) 중에서 최대값을 찾으며 된다.

#include<stdio.h>
#define MAX(A,B) (A>B)?A:B
 
void swap(int *A, int *B) {
    int temp;
 
    temp = *A;
    *A = *B;
    *B = temp;
}
 
int partition(int *A, int p, int r) {
    int i = p - 1;
 
    for (int j = p; j < r; j++) {
        if (A[j] < A[r]) {
            swap(&A[++i], &A[j]);
        }
 
    }
    swap(&A[i + 1], &A[r]);
 
    return i + 1;
}
 
void quickSort(int *A, int p, int r) {
    int q;
 
    if (p < r) {
        q = partition(A, p, r);
        quickSort(A, p, q - 1);
        quickSort(A, q + 1, r);
    }
}
 
int main() {
    int n, *rope;
    int Wmax = 0;
 
    scanf("%d",&n);
 
    rope = (int *)malloc(sizeof(int)*n);
    for (int i = 0; i < n;i++) {
        scanf("%d",&rope[i]);
    }
    quickSort(rope,0,n-1);
 
    for (int i = 0; i < n;i++) {
        Wmax = MAX(Wmax, rope[i] * (n-i));
    }
 
    printf("%d\n",Wmax);
 
    return 0;
}