백준 1182번: 부분수열의 합 - javascript

2 분 소요

백준 1182번: 부분수열의 합

문제 설명

접기/펼치기

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

입력

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

출력

접기/펼치기

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

예시

접기/펼치기

입력
5 0
-7 -3 -2 5 8

출력
1

접근

이것 역시 비트마스크를 활용한 문제인데, 나는 11723번: 집합의 경우와 마찬가지로 비트마스크를 쓰지 않고 boolean으로 풀었다.
~~사실 비트마스크나 boolean배열이나 결국 인덱싱하는데 있어서 o(1)의 시간을 활용하여 메모리 사용량을 줄여보기 위한 문제아닌가?~~
문제의 기본 풀이방식은 n과m(2)를 참고했다.
하지만 매번 링크를 걸어놓으면 보기에 불편하실테니, 처음부터 설명하고자 한다.

먼저 우리는 주어진 정수 N개를 가지고 모든 부분집합을 구해서 그 부분집합의 합이 정수 S와 같은지 확인하여 같은 경우의 횟수를 출력하는 것이 목적이다.

그럴려면 정수 N개로 이루어진 수열의 모든 부분 집합을 구해야한다.
이는 재귀함수를 사용해서 만들 수 있다.

i를 0부터 N까지 시행하는 반복문을 만든다.
i를 고른 뒤 전역배열 list의 현재 깊이에 i를 넣고 재귀호출한다.
2.1. 이때 boolean 배열인 check를 두어 i번째 값을 true로 바꾸어 중복을 방지한다.
2.2. 그리고 재귀호출 할 때 i값을 넘겨주어 오름차순으로만 부분집합이 구해지게 두어 부분집합의 중복을 방지한다. 2.3. 깊이가 N까지 재귀호출되었으면 현재까지의 list배열을 다른 결과값 배열 result에 join으로 넣어 값에 의한 참조를 시켜 저장한다. 2.4. 이후 반환문을 호출해서 재귀를 멈춘다.
list를 출력하면 모든 부분집합이 나온다.

…의 과정인데, 여기서 list 배열을 매번 출력하고 result 배열에 저장하고 하면 메모리 사용량이 늘어날 것이다.
그리고 우리는 매번 선택값을 갖고있는 boolean 배열이 있다.
따라서 위에서 2) 전역배열 list에 i값을 넣어주는 부분을 과감하게 삭제한다.
그리고 2.3)result배열도 없애버린다.

대신에, 깊이가 1이상일때마다 현재까지의 부분집합의 합을 주어진 정수 S와 비교하는 함수를 호출한다.

생각해보자, N이 5일때 1번째 값을 고른다.
그리고 그 뒤로 나올 수 있는 부분집합은 다음과 같다.
[1, 12, 123, 1234, 12345, 13, 134, 1345, 14, 145, 15]
이 모든것은 1로부터 시작된다.
그래서 깊이가 1이상이면 부분집합의 합과 정수 S를 비교하는 것이다.
(boolean 집합은 어디에 따로 결과를 저장하지 않기 때문에 그때그때 함수를 호출해서 값을 비교해줘야한다.)

부분집합의 합을 정수 S와 비교해주는 함수는 간단하다.
i를 0부터 n까지 반복문을 돌려서 check[i]값이 true일때만 주어진 배열의 i번째 값을 더하는 것이다.
전부 더 한 뒤에 정수 S와 비교해서 같으면 true를 반환해주고 아니면 false를 반환해주면 된다.

그리고 최종적으로 이 함수를 호출할때마다 true값이 반환되면 전역 카운터값을 1 올려주고, 재귀호출이 전부 끝나면 이 전역카운터 변수값을 출력하면 답이 나온다.

ps
아, 비트마스크로 푸는 방법은 안만들었는데, 생각해보면 중복체크 배열 check를 사용하는 부분에서 현재의 i값이 있는지 중복체크는 and로, 추가는 or로 해주면 될 것 같다.
오히려 비트마스크를 사용하면 전역배열이 아니라 그냥 매개변수로 넘겨줄 수 있지않을까?… 라는 생각이 든다.

부분집합의 합을 구할때에도 i를 0부터 n까지 반복문을 돌리면서 현재 비트값에 2의i승 값이 and로 존재 할 때만 합에 주어진배열의 i번째 값을 더하도록 하면 똑같이 돌아갈 것이다.

정답 코드

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
let input = [];
let list = [];
let check = new Array(20).fill(false);
let numbers = [];
let result = 0;
rl.on('line', function (line) {
  input.push(line);
})
  .on('close', async function () {
  // 답안 작성
  let first_line = input[0].split(' ')
  const n = first_line[0]*1;
  const s = first_line[1]*1;
  numbers = input[1].split(' ').map(el => parseInt(el));
  re(0,n,s,-1);
  console.log(result);    
  process.exit();
});

let sum_check = function(n,s){
  let sum = 0;  
  for(let i=0;i<n;i++){    
    if(check[i])sum+=numbers[i];    
  }  
  if(sum==s)return true;
  return false;
}

let re = function(cnt,n,s,back){    
  if(cnt>0&&sum_check(n,s))result++;
  if(cnt===n)return ;
  for(let i=0;i<n;i++){   
    if(!check[i]&&back<i){
      check[i] = true;
      re(cnt+1,n,s,i)
      check[i] = false;
    }
  }
  return ;
}

Twitter Facebook LinkedIn

ryeon

백준 1182번: 부분수열의 합 - javascript