백준 1450 냅색 문제 (이분 탐색)

문제

제한 사항

입출력 예

풀이

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');

const sol = (input) => {
  const [n, maxWeight] = input[0].split(" ").map(Number);
  let weights = input[1].split(" ").map(Number);
  const weightA = weights.slice(0, parseInt(weights.length / 2));
  const weightB = weights.slice(parseInt(weights.length / 2));

  let sumA = [];
  let sumB = [];
  const dfs = (arr, sumArr, L, sum) => {
    if (L === arr.length) {
      sumArr.push(sum);
      return;
    } else {
      dfs(arr, sumArr, L + 1, sum);
      dfs(arr, sumArr, L + 1, sum + arr[L]);
    }
  };
  dfs(weightA, sumA, 0, 0);
  dfs(weightB, sumB, 0, 0);
  sumB.sort((a, b) => a - b); // 이분탐색을 해주기 위해.

  const binarySearch = (arr, target, start, end) => {
    while (start < end) {
      let mid = Math.floor((start + end) / 2);
      if (arr[mid] <= target) {
        start = mid + 1;
      } else {
        end = mid;
      }
    }
    return end;
  };

  let cnt = 0;

 
for (let x of sumA) {
    const target = maxWeight - x;
    if (target < 0) {
      continue;
    }

    cnt += binarySearch(sumB, target, 0, sumB.length);
  }

  return cnt;
};

console.log(sol(input));

• 솔직히 잘 모르겠다. 일단 패턴을 외우도록 하자.
• 배열을 반으로 나눈다.
• 각 집합의 부분집합의 합을 포함하는 배열을 만들고 하나는 정렬해준다.
• 이분탐색으로 조건을 만족하는 부분집합의 개수를 구한다.