https://www.acmicpc.net/problem/2217
2217번: 로프
N(1≤N≤100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다. 각 로프들에 대한 정보가 주어졌을 때, 이 로프들을
www.acmicpc.net
로프를 k개 (1 <= k <= n) 만큼 사용하는 경우 로프들을 이용해서 들 수 있는 중량을 모두 구해서 그중 최댓값이 최대 중량이 된다.
먼저 1개만 사용하는 경우에는 들 수 있는 중량이 가장 큰 로프의 경우가 최댓값이다.
그리고 2개만 사용하는 경우에는 들 수 있는 중량이 가장 큰 로프와 두번째로 큰 로프 두 개를 사용하여야 들 수 있는 최대 중량을 만들 수 있을 것이다. 이런식으로 k개의 로프를 사용하는 경우에는 들 수 있는 중량이 가장 큰 로프 k개를 사용하는 것이 최댓값이므로 로프를 내림차순으로 정렬해준다.
그리고 문제에서
k개의 로프를 사용하여 중량이 w인 물체를 들어 올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.
라고 하였으므로 k개를 사용할 때는 (가장 작은 로프의 값 X k) 만큼이 들어올릴 수 있는 중량이다.
이렇게 k개를 사용하는 모든 경우의 중량 중 최대 중량이 정답이다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
#include<iostream>
#include <algorithm>
using namespace std;
int arr[100000];
bool comp(int a, int b) {
//내림차순
return a > b;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
//내림차순 정렬
sort(arr, arr + n, comp);
//처음에 가장 큰 값(0번째 값)을 저장
int ans = arr[0];
for (int i = 1; i < n; i++) {
if (ans < (arr[i] * (i + 1))) {
ans = (arr[i] * (i + 1));
}
}
cout << ans << '\n';
return 0;
}
Colored by Color Scripter
|
'BOJ' 카테고리의 다른 글
| [BOJ] 6359. 만취한 상범 (0) | 2019.09.04 |
|---|---|
| [BOJ] 1931. 회의실배정 (0) | 2019.09.02 |
| [BOJ] 1541. 잃어버린 괄호 (0) | 2019.09.02 |
| [BOJ] 11729. 하노이 탑 이동 순서 (0) | 2019.08.31 |
| [BOJ] 별 찍기 - 10 (0) | 2019.08.31 |