99클럽 코테 스터디 9일차 TIL - 저울 (그리디)

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

문제 요약

양팔 저울과 N개의 저울추가 주어질 때,
이 추들을 이용해 측정할 수 없는 가장 작은 양의 정수 무게를 구하는 문제

그리디 알고리즘(매 순간 최선의 선택을 해서 전체 문제를 해결하는 방식) 문제이다.

접근 방식

• 지금까지 만들 수 있는 연속된 무게의 끝을 target이라고 할 때,
  새로운 추가 target보다 크면, 그 target은 절대 만들 수 없다
• 즉, target보다 작은 추만 있으면 target까지의 모든 무게를 만들 수 있다

구현

const fs = require("fs")
const [n, str] = fs.readFileSync("/dev/stdin").toString().trim().split("\n")
const arr = str.split(" ").map(Number).sort((a, b) => a - b)

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

console.log(target)