백준 2217 - 로프

진짜 이것때문에 운동도 못가고....(사실 가기싫었음)

문제

---

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

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

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

풀이

• 일단 내림차순으로 정렬해야함 - 당연히 무게 많이 버티는 로프가 중량 많은 로프를 들 수 있기 때문에

• 10000 1 이라는 로프 두개가 있다고 하면 이 로프 두개는 병렬 연결하는게 손해임 - 이렇게 병렬 연결하는 게 손해인 로프가 존재함

그렇다면 생각해볼 수 있는 게 일단 제일 무거운 로프(제일 하중 많이 견디는) 하나 쓰는게 최선이라고 가정하고, 내림차순 한 로프 배열을 하나씩 돌면서 내가 이 다음 로프와 병렬 연결하는 게 이득인지 아닌지를 판단해주면 됨

for (let i = 1; i < n - 1; i++) {
  if (input[i] * (병렬 + 1) > max) {
    max = input[i] * (병렬 + 1);
    병렬 += 1;
  } else {break}
}

그렇게 짠 게 이 코드인데, 만약 병렬 연결해서 손해인 코드를 만나면 종료했지만 (어차피 내림차순이라 괜찮을 줄 알았음) 치명적인 반례가 있음(꼭 그 반례때문에 틀린건 아니긴함)

ex) 10 3 3 3 - 10과 3을 병렬연결하면 10이 손해지만 , 전체 4개를 병렬연결 할 경우에는 12라는 값이 나온다는 사실

const fs = require("fs");
let input = fs
  .readFileSync("./test.txt")
  .toString()
  .trim()
  .split("\n")
  .map((v) => +v);
const n = input.shift();
input.sort((a, b) => b - a);
let 병렬 = 1;
let max = input[0];
for (let i = 1; i < n; i++) {
  max = Math.max(max, input[i] * ++병렬);
}
console.log(Math.max(...input) > max ? Math.max(...input) : max);

이 코드는 병렬 연결하는게 손해라면 종료하는 게 아니라 다시 또 연결해서 만약 이득일 경우가 나오면 max값으로 변경해줌 - n도 최대 10만이라 괜찮고 이게
훨씬 안전한 방식

• 사실 생각해보면 몇 개를 쓰는게 이득이냐 라고 물어보진 않음...
• 콘솔에 조건식은 사실 필요 없음