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

목차

 문제

링크

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

문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

 

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

 

주저리

비트마스크 방식으로 해결하였다

부분수열의 전체집합의 갯수는 2 ^ N개 이므로 브루트 포스를 이용해서 for문을 돌려 이진수화시켜 비트가 1인 갯수들을 합쳐줘서 S가 나오는지 계산해주고 나올때마다 1씩 더해주면 된다.

 

풀이

 부분수열의 합 계산

• 이 함수는 배열의 모든 가능한 부분수열을 생성하여 각 부분수열의 합이 S와 같은지 검사합니다.
• 2 ** N은 부분수열의 총 개수를 나타내며, 각 부분수열은 이진수 인덱싱을 통해 표현됩니다. i.toString(2).padStart(N, '0')는 숫자 i를 이진수 문자열로 변환하고, 필요한 경우 앞에 0을 채웁니다.
• 각 비트가 1인 경우 해당 인덱스의 숫자를 포함시키고, 0인 경우 포함시키지 않습니다.
• 최종적으로, 부분수열의 합이 S와 동일하면 카운트를 증가시킵니다.

 

 코드

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

let real = input.trim().split("\n");
let [first, rest] = real;
let [N, S] = first.split(" ").map(Number);
rest = rest.split(" ").map(Number);
// rest = rest.map((row) => {
//     row = row.trim().split(" ").map(Number);
//     return row;
// })


// console.log({ N, S, rest });

async function solution() {
    let returns = 0;
    for (let i = 1; i < 2 ** N; i++) {
        let i2 = i.toString(2).padStart(N, '0')
        let fi = [...i2].map((bit, i) => {
            if (bit === '1' || bit === 1) {
                return Number(rest[i])
            }
            else {
                return 0
            }
        })
        let sum = fi.reduce((acc, cv) => acc + cv, 0)

        if (sum === S) {
            returns++;
        }
    }

    console.log(returns);

}
solution();