[c++] 백준 2217: 로프

[c++] 백준 2217: 로프

🥈실버 4

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

2217번: 로프

---

접근

중량이 어쨌든 간에 중요한 것은 두가지이다.

1. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개만 골라도 된다.

2. 각각의 로프에는 모두 고르게 w/k 만큼의 중량만 걸린다.

 

예제 입력1을 그림으로 나타내면 다음과 같다.

 

위의 경우에는 다음과 같은 경우의 수로 물체를 들어올릴 수 있다.

1. 15kg 로프 하나로 든다. > 15 * 1 = 15

2. 15kg 로프 하나와 10kg 로프 하나로 든다. > 이 경우 각 로프는 같은 중량의 무게가 걸리게 되므로 10 * 2 = 20

1번과 2번의 경우 최댓값은 20이므로 예제 입력1의 경우에는 최대 중량이 20kg가 되는 것이다.

 

다음의 경우를 살펴보자.

위의 경우에는 다음과 같은 경우의 수로 물체를 들어올릴 수 있다.

1. 50kg 로프 하나로 들기 > 50

2. 50, 30 로프 총 두개로 들기 > 30 * 2 = 60

3. 50, 30, 15 로프 총 세개로 들기 > 15 * 3 = 45

4. 전부 다 동원해서 들기 > 10 * 4 = 40

이 네가지 경우의 수 중 가장 크게 들 수 있는 것은 60이므로 정답으로 60이 출력되어야 한다.

 

이를 구현하기 위한 접근은 다음과 같다.

1. 입력 받은 값을 배열에다가 내림차순으로 정렬한다.

2. 가장 큰 무게는 로프 하나만, 그다음 무게에는 2개, 그 다음 무게에는 3개... 이런식으로 계산하고

최댓값을 갱신한다.

3. 최댓값을 정답으로 출력한다.

 

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin >> N;
  int arr[N];
  for (int i = 0; i < N; i++) {
    cin >> arr[i];
  }
  sort(arr, arr+N, greater<>());
  int weight = -1;
  for (int i = 0; i < N; i++) {
    weight = max(weight, arr[i] * (i+1));
  }
  cout << weight;
  return 0;
}