[백준] 14225. 부분수열의 합

문제 링크

[백준] 14225. 부분수열의 합

풀이 과정

다음은 시간을 단축시킬 수 있는 직관적인 풀이 방법입니다.

아래 예시를 통해 풀이 방법을 살펴보겠습니다.

현재 살펴볼 숫자를 의미하는 변수 num 을 가장 작은 자연수인 1로 초기화하고 첫 번째 요소부터 확인합니다. num 은 arr[0] 과 같고, 이는 1을 만들 수 있음을 의미합니다. 따라서, num 에 1을 더한 2를 다음 요소와 비교합니다.

현재 num 은 2입니다. 이는, 자연수 2를 만들 수 있는지를 확인하는 단계임을 의미합니다. num 은 arr[1]과 같고, 2를 만들 수 있음을 의미합니다. num 에 2를 더해 4를 만들고, 다음 요소와 비교합니다.

현재 num 은 4입니다. num 이 arr[2]와 같고, 이는 자연수 4를 만들 수 있음을 의미합니다. num 에 4를 더해 8을 만듭니다.

배열의 순회가 끝났습니다. 1, 2, 4로 만들 수 없는 최소 자연수는 8이고, 이는 num 값과 같게 됩니다. 따라서, num 을 출력합니다.

const fs = require("fs");
const stdin = (process.platform === "linux"
    ? fs.readFileSync("/dev/stdin")
    : `3
5 1 2`
)
    .toString()
    .trim()
    .split("\n");
const input = (() => {
    let line = 0;
    return () => stdin[line++];
})();

const N = +input();
const arr = input().split(" ").map(Number);
let num = 1;
arr.sort((a, b) => a - b);

for (let idx in arr) {
    if (num < arr[idx]) break;
    num += arr[idx];
}

console.log(num);

완전 탐색을 통해 모든 만들 수 있는 모든 수열의 합을 구할 수 있습니다.

let made = Array(2000001).fill(false);

변수 made 는 수열의 모든 경우의 수를 통해 만들어진 값을 체크하기 위한 배열입니다. 수열의 최대 크기가 20이고, 각 요소의 최대값이 10만이므로, 만들 수 있는 수열의 최대 합은 20만이 되므로, 배열 크기를 200001로 정했습니다.

dfs(0, 0);

function dfs(idx, sum) {
    if (idx == N) {
        made[sum] = true;
        return;
    }

    dfs(idx + 1, sum);
    dfs(idx + 1, sum + arr[idx]);
}

dfs 메소드 는 부분 집합을 구하며, 선택한 요소 값을 누적해 나갑니다. 마지막 인덱스를 가리킬 때, 누적된 값 sum 을 인덱스로 배열 made 에 해당하는 요소를 체크해 둡니다.

let num = 1;

while (true) {
    if (made[num]) {
        num++;
        continue;
    }

    console.log(num);
    break;
}

자연수 1부터 시작해, 만들지 못한 수를 찾아 출력합니다.

코드

const fs = require("fs");
const stdin = (process.platform === "linux"
    ? fs.readFileSync("/dev/stdin")
    : `3
5 1 2`
)
    .toString()
    .trim()
    .split("\n");
const input = (() => {
    let line = 0;
    return () => stdin[line++];
})();

const N = +input();
const arr = input().split(" ").map(Number);
let made = Array(2000001).fill(false);
let num = 1;

dfs(0, 0);

while (true) {
    if (made[num]) {
        num++;
        continue;
    }

    console.log(num);
    break;
}

function dfs(idx, sum) {
    if (idx == N) {
        made[sum] = true;
        return;
    }

    dfs(idx + 1, sum);
    dfs(idx + 1, sum + arr[idx]);
}