문제

N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.

하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.

각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.

입력

첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.

출력

첫째 줄에 답을 출력한다.

예제 입력

2
10
15

예제 출력

20

내가 했던 풀이 방법

1. 로프들 내림차순으로 정렬해준다.
2. 들 수 있는 가장 무거운 무게를 max에 저장한다.
3. ropes의 1부터 끝까지 반복하면서, 현재 ropes를 min으로 하고, 그 앞에 있는 ropes를 모두 이용해서 물체를 들어올린다고 하자. 이 경우, 현재 min에 저장된 로프를 제외한 나머지 rope의 갯수는 i개이다. 그러므로, 총 갯수는 i+1이다. 이 경우 들 수 있는 최대의 중량은 i+1개의 min값을 곱해준 값이다. 이 경우가 max보다 큰 경우, max를 바꿔준다.
4. max를 출력한다.

코드

const fs = require('fs');
let [N, ...ropes] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

N = Number(N);
ropes = ropes.map((value) => Number(value));
ropes.sort((a, b) => b - a);

let max = ropes[0];

for (let i = 1; i < N; i++) {
  let min = ropes[i];
  let maxWeight = min * (i + 1);
  if (maxWeight > max) max = maxWeight;
}

console.log(max);

회고

코드만 보면 어렵지 않고, 실제로 해당 풀이 방법을 생각하기까지 1분도 안 걸렸다. 그럼에도 기록하는 이유는 물체의 중량이 항상 다르기만 하지 않다는 것이다. 같을 경우도 고려해야 한다.

9
5
2
1
1
1
1
1
1
1

해당 입력은 처음 구현했을 때 정답이 다르게 나왔던 반례이다. 이때 정답은 9이다. 물체의 중량이 같을 수 있다는 것을 고려하지 않고, max값보다 maxWeight가 작으면 for문을 중단해주는 조건을 처음에 걸어줬다. 하지만, 다음과 같이 갯수가 많을 경우 오히려 중량이 작아도 갯수가 많아져서 더 많이 들 수 있다는 것이다. 그렇기 때문에 반복문을 중단하면 안 되고, 끝까지 모든 경우를 확인해줘야 한다. 연산을 좀 더 빠르게 해결하려고 하다보니 욕심이 났던 케이스였던 것 같다.