[백준] 14225번 부분수열의 합 _ Node.js

 

문제

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

14225번: 부분수열의 합

 

---

문제 풀이

 해당 문제는 부분 수열로 나타낼 수 없는 수 중 가장 작은 수를 출력하는 문제이다. 해당 문제는 조합으로 부분 수열을 탐색이 가능하지만 간단하게 이진수로 나타내어 풀었다.

 

부분 수열은 해당 수열의 요소가 존재하거나 안하거나로 나타낼 수 있다. 부분 수열에 존재 할 때는 1, 아닐 경우는 0으로 나타낸다. 문제의 1번 예제를 예로 들어보면 아래와 같다.

 

해당 방법을 통해 부분 수열을 구하고 부분 수열의 합을 미리 선언한 배열에 1로 존재한다고 저장한다.

 

for(let i = 1; i < Math.pow(2,n);i++){
    let binary = i.toString(2).split('').map(Number);
    if(binary.length !== n)   binary = Array(n - binary.length).fill(0).concat(binary)
    let sum = binary.reduce((x,v,j)=> (v * numList[n - 1 - j]) + x,0)
    answer[sum]= 1 ;
}

위 코드는 2진수를 배열로 변환하는 과정이다. 이 때 변환된 2진수의 자릿수가 작다면 if문과 같이 자릿수를 맞추어 주어야 한다. 이 과정을 진행하지 않을 경우는 정상적으로 작동하지 않고 중복된 수가 나오게 된다.

 

모든 부분 수열의 계산이 끝난다면 배열의 빈 부분 중 가장 작은 작은 수를 출력한다.

 

풀이 코드

const fs = require('fs');
const stdin = (process.platform === 'linux'? fs.readFileSync('/dev/stdin').toString() :
`4
2 1 2 7`).split('\n');

const input = (() => {
    let line = 0;
    return () => stdin[line++];
})();

const n = Number(input());
const numList = input().split(' ').map(Number);
let answer = Array(100010 * n).fill(0);
let search = 1;

for(let i = 1; i < Math.pow(2,n);i++){
    let binary = i.toString(2).split('').map(Number);
    if(binary.length !== n)   binary = Array(n - binary.length).fill(0).concat(binary)
    let sum = binary.reduce((x,v,j)=> (v * numList[n - 1 - j]) + x,0)
    answer[sum]= 1 ;
}

while(true){
    if(!answer[search]){
        console.log(search);
        break;
    }
    search++;
}