BOJ_2437 저울

• TOC {:toc}

이 글은 백준 온라인 저지의 2437번 문제를 자바스크립트(JavaScript)으로 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2023.02.27

const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

const [N, line] = input;
const weights = line
    .split(" ")
    .map((n) => parseInt(n))
    .sort((a, b) => a - b);

function main() {
    let max = 0;
    for (let i = 0; i < N; i += 1) {
        if (weights[i] > max + 1) {
            return max + 1;
        }
        max += weights[i];
    }
    return max + 1;
}

console.log(main());

아이디어 & 풀이

구체적인 풀이 아이디어는 다음의 글을 참고해주시길 바랍니다.

• 백준 2437 풀이 및 해설 by AeroCode

작은 수부터 순회하면서 각 값을 더해 숫자의 구간을 만든다고 했을 때, 해당 값까지 더해서 만들 수 있는 최댓값보다 다음에 더하는 수가 생기면 구간에 공백이 생긴다.

주어진 예제를 이용해 (1 1 2 3 6 7 30) 각 수를 순회하면서 만들 수 있는 수를 살펴보자.

• 1: 1
• 1: 1, 2(1 + 1)
• 2: 1, 2, 3(1 + 2), 4(2 + 2)

이 상태에서 다음의 수가 각각 4, 5, 6인 경우를 생각해보면

• 4: 현재 1, 2, 3, 4가 있으므로 각 값에 4를 더하면 5, 6, 7, 8이 되므로 연속된 구간을 만들 수 있다.
• 5: 각 값에 5를 더하면 6, 7, 8, 9가 되지만 자기 자신이 5이므로 1, 2, 3, 4 뒤에 5, 6, 7, 8, 9가 이어지는 연속된 구간을 만들 수 있다.
• 6: 각 값에 6을 더해서 만들 수 있는 구간은 6, 7, 8, 9, 10으로 1, 2, 3, 4에 연속되지 않는다.

위의 결과를 정리하면

• 현재 만들 수 있는 최댓값 4와 비교했을 때,
  • 이 값은 이전까지 주어진 수를 모두 더한 값과 같다 (1 + 1 + 2).
• 주어진 수가 그 값에 1을 더한 5보다 큰 값이면 연속된 구간을 만드는 것이 불가능하고
• 이 때 처음으로 등장하는 만들 수 없는 수는 5이다.

이를 일반화해서 정리하면 다음과 같다.

if (weights[i] > max + 1) {
    return max + 1;
}