[백준] 2437 저울 - javascript

📌 문제

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

📌 풀이

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");

const n = +input[0];
const arr = input[1]
  .split(" ")
  .map(Number)
  .sort((a, b) => a - b);

let ans = 0;
for (let i = 0; i < n; i++) {
  if (arr[i] > ans + 1) {
    break;
  }
  ans += arr[i];
}

console.log(ans + 1);

✔ 알고리즘 : 그리디

✔ 측정 가능한 무게가 끊기지 않는다는 점에 포커스를 두고 문제에 접근하였다.

예를들어 현재 1~5 까지 무게를 잴 수 있고 다음 추가 4라고 한다면 1+4 ~ 5+4 까지 무게를 잴 수 있게 된다. 따라서 현재까지 잴 수 있는 무게보다 다음 추가 크다면 측정 가능한 무게가 무조건 끊기게 된다. 여기선 ans 변수값이 현재 추들로 측정 가능한 무게의 최댓값이다.

if (arr[i] > ans + 1) {
  break;
}

✔ 측정이 불가능한 무게를 출력해야 하므로 측정가능한 무게+1을 출력해준다.

✔ 난이도 : 백준 기준 골드 3