알고리즘/백준
백준 2217 로프 c++ [컴공과고씨]
시간빌게이츠
2022. 3. 24. 20:20
반응형
https://www.acmicpc.net/problem/2217
2217번: 로프
N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하
www.acmicpc.net
이 문제는 어떤 식으로 접근했냐면 한 로프를 사용한다고 가정했을 때, 자기보다 많은 무게를 드는 로프는 결국 자신의 로프의 최대 들 수 있는 용량을 모두 들 수 있다는 것을 이용했다.
10 30 50 50 85 90 이라는 무게를 들 수 있는 로프가 있을 때 10로프를 이용해서 들 수 있는 최대 중량은? 10과 10보다 큰 로프의 개수를 10에 곱해주면 총 60을 들 수 있다. 30로프를 이용할 때는? 30과 30보다 큰 로프 즉, 30보다 큰 로프의 개수 +1에 자신이 들 수 있는 무게 30을 곱해주면 된다. 이렇게 해서 각 로프를 이용할 때 들 수 있는 최대 용량을 구해서 각각의 값들에서 가장 큰 값이 모든 로프에서 들 수 있는 최대 중량이 된다.
정리하면 A용량의 로프를 이용할 때 들 수 있는 최대 용량은
(A가 들 수 있는 최대 용량)*(A보다 큰 용량의 로프의 개수 + 1) 이 된다.
전체코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
long long loap[100001];
int n;
cin >> n;
for (int i = 0; i < n;i++){
cin >> loap[i];
}
sort(loap, loap + n); // 오름차순 정렬
long long most = 0;
for (int i = 0; i < n;i++){
if(most < loap[i]*(n-i)){
most = loap[i]*(n-i); // (자기가 들 수 있는 최대 용량)*
(자기보다 큰 용량의 로프의 개수 + 자신) }
}
cout << most;
return 0;
}
|
cs |
사용알고리즘 : sort
yea!
반응형