[백준] 2217_로프(C++)

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

2217번: 로프

이 친구는 좀 쉬웠는데,,
왜 안 됐을까 아직도 모르겠다.

나는 정렬하기 귀찮아서 set을 썼었는데,,
틀렸다,,
set이랑 배열이랑 무슨 상관일까?
포인터로 접근해서 그런가,,,,,,,,

set 말고 배열로 할당받아 계산하니 됐다.

이 알고리즘은 엄청 간단하다.

• 정렬한다.
• 정렬한 첫번째 값(젤 작은 값 ) * testcase랑 곱한다.
• testcase는 감소하면서 두 번째 값을 곱한다.
• 젤 큰 값을 찾는다.

이렇게 하는 이유가,
로프는 전체를 쓸 필요가 없고, 들어올릴 수 있는 최대 중량을 구하는 것이다.

---

생각해보면 간단하다.
예를 들어
40
100
2
5000
무게를 들 수 있는 로프가 있다.

정렬을 안 해보고 생각해보자
40 부터 1개니깐, 무게는 40
40,100 개를 들면, x/2 = 40(최소 40들 수 있음) → 최대 80
40, 100, 2이면 : x/3 = 2(최소 2 들 수 있음) → 최대 6
40, 100, 2, 5000 : x/4 = 2(최소 2 들 수 있음) → 최대 8

여기서 젤 큰 값은 80이다.
따라서 최댓값은 80이다.
로프를 전부 포함 안 해도 된다고 했으니
이런 결과값이 나올 수 있다.

#include<iostream> #include <set> #include <algorithm> using namespace std; int main() { int input[100001]; int testcase; cin >> testcase; long long max_num = 0; for (int i = 0,num; i < testcase; i++) { cin >> num; input[i] = num; } sort(input, input + testcase); for (int i = 0,mul = testcase; i < testcase; i++) { long long cal_num = (mul--) * input[i]; if(max_num < cal_num) max_num = cal_num; } cout << max_num; return 0; }