[node.js, 백준]14225 - 부분수열의 합

목차

 

 

 문제

링크

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

문제

수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오.

예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 수 있다. 하지만, 4는 만들 수 없기 때문에 정답은 4이다.

입력

첫째 줄에 수열 S의 크기 N이 주어진다. (1 ≤ N ≤ 20)

둘째 줄에는 수열 S가 주어진다. S를 이루고있는 수는 100,000보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 출력한다.

 

주저리

부분수열의 합으로 부분수열의 합이 아닌것 중 제일 작은 자연수 찾는 문제이다.

수는 중복으로 나올수있고 그 부분을 해결하기위해 boolArray라는 그 수를 사용했는지 여부를 체크하였고

부분수열의 합들은 checkArray에 담아주었다.

그렇게 go함수를 다 수행한후 while문을 거쳐 작은수부터 부분수열이 합이아닌지를 체크해주면 된다.

 

풀이

 입력 처리

• 테스트를 위해 입력을 하드코딩 하였으며, 숫자 배열은 오름차순으로 정렬합니다.

 초기화

• 최대 합을 계산하고, 각 합이 나타났는지 여부를 추적하는 checkArray를 초기화합니다.

 백트래킹 함수 'go'

• 현재 인덱스와 현재까지의 합, 그리고 수열 내에서의 현재 위치를 인자로 받아 재귀적으로 부분수열의 합을 계산합니다.

 코드

// 부분수열의 합
var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString();

let real = input.trim().split("\n");
let [N, S] = real;
N = Number(N);
let numArray = S.split(" ").map(Number).sort((a, b) => a - b);
let numArrayLength = numArray.length;
let maxSum = numArray.reduce((acc, cv) => acc + cv, 0);
let checkArray = Array.from({ length: maxSum }).fill(false);
let boolArray = Array.from({ length: numArray.length }).fill(false);

function go(index, sum, cnt) {
    if (index === numArrayLength + 1) return;
    for (let i = cnt; i < numArrayLength; i++) {
        if (boolArray[i]) continue;
        let num = sum + numArray[i];
        // if (checkArray[num - 1]) continue;
        boolArray[i] = true;
        checkArray[num - 1] = true;
        // console.log({ index, sum, num, boolArray })
        go(index + 1, num, i);
        boolArray[i] = false;
    }
}

async function solution() {
    go(0, 0, 0);
    // console.log({ checkArray, boolArray })
    let index = 0;
    while (true) {
        if (!checkArray[index]) {
            console.log(index + 1)
            return;
        }
        index++;
    }

}
solution();