[BaekJoon] 41225 번 부분수열의 합 문제 - (nodejs)

문제 번호 :  14225 번

문제 바로가기 ☞ https://www.acmicpc.net/problem/14225

---

 

<<< 문제 내용 >>>

---

 

const fs = require('fs');
const { deflateSync } = require('zlib');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n');

let tables = new Array(2000001).fill(false);

const N = Number(input.shift());
const S = input[0].split(' ').map(Number);

const dfs = (idx, sum, arr) => {
    if(idx == N){
        tables[sum] = true;
        return;
    }

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

dfs(0, 0, S);

for(let i=1; i<tables.length; i++){
    if(!tables[i]){
        console.log(i);
        break;
    }
}

* 1,2,3,5가 있을 때, 1+2, 1+3, 1+5, 1+2+3, 1+2+5, 1+3+5 ... 1+2+3+5 처럼 모든 경우의 수를 찾아내는 방식은 dfs를 사용하여야 합니다.

 

그리고 빈 값을 찾는 방법은 두 가지가 떠올랐는데,

 

첫번째는 ' 모든 값을 배열에 넣은 후, 정렬하고 while문 안에서 빈 값을 찾을 때 까지 반복 ' 과

 

두번째로는 문제의 S의 범위가 10만보다 작기 때문에 N의 20번이 반복되어도 절대 200만이 넘지 않습니다.

그래서 기존에 false인 200만 개의 자료를 담을 수 있는 배열을 선언 후 dfs가 마지막에 도달하면, 현재의 값을 true로 바꿔줍니다.

 

그리고 200만개를 돌아가며 false를 찾아서 출력하면 됩니다.

 

 

 

 

도움이 되셨다면 공감 부탁드립니다.