문제

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

최대한 많은 곡을 칠수있는 기타의 개수를 구하는 문제다.

입력

• 첫째줄 기타개수 N, 곡의개수 M
  • $1 \leq N \leq 10$, $1 \leq M \leq 50$
• 둘쨰줄 ~ N번째줄 기타의 이름과, 연주할수 있는 곡 정보 1번부터 차례대로 주어짐
  • Y는 연주할수 있는곡, N는 연주할수 없는곡

정답코드

const stdin = require('fs').readFileSync(0, 'utf-8')
  .trim()
  .split('\n');
const input = (() => {
  let line = 0;
  return () => stdin[line++].split(' ');
})();

const [N, M] = input().map(Number);
const guitars = [];

let guitarNum = -1;
let songNum = -1;

for (let i = 0; i < N; i++) {
  const [_, song] = input();
  guitars.push(
    BigInt(
      '0b' +
        song
          .split('')
          .map(v => (v === 'Y' ? 1 : 0))
          .join(''),
    ),
  );
}

const recur = (end, start = 0, arr = [], sum = 0n) => {
  if (sum > 0) {
    const songCnt = sum.toString(2).match(/1/gi).length;
    const guitarCnt = arr.length;

    if (songCnt > songNum || (songCnt === songNum && guitarCnt < guitarNum)) {
      songNum = songCnt;
      guitarNum = guitarCnt;
    }
  }
  if (arr.length === end) {
    return;
  }

  for (let i = start; i < N; i++) {
    recur(end, i + 1, [...arr, i], sum | guitars[i]);
  }
};

for (let i = 0; i <= N; i++) {
  recur(i);
}
console.log(guitarNum);

해설

우선 이 문제는 비트마스킹 + 조합으로 푸는 문제다.

근데 자바스크립트로 이진수로 변환을 해본적이 그렇게 많지 않아서 많이 헤맸다.
그리고 큰 수를 입력받는 부분도 헤맸기에 3시간이 걸려버렸다..
하지만 다음부터는 이번 기회를 바탕으로 빠르게 풀수 있을거라 생각한다.
잡설은 여기까지하고 코드를 보면

---

for (let i = 0; i < N; i++) {
  const [_, song] = input();
  guitars.push(
    BigInt(
      '0b' +
        song
          .split('')
          .map(v => (v === 'Y' ? 1 : 0))
          .join(''),
    ),
  );
}

위의 코드에서 입력받은부분을 Y는 1로, N은 0으로 변환후에 2진수로변환해서 BigInt에 넣어준다.
자바스크립트에서 비트연산은 32비트로 수행하기 때문에 232,
10진수로 4294967296이넘는 값,
2진수로 100 0000000000 0000000000 0000000000가 넘는 값을 비트연산할경우
32비트까지만 표기된다. 하지만 N은 최대 50이기때문에 BigInt로 넣어줘야 제대로된 연산이 가능하다.

---

for (let i = 0; i <= N; i++) {
  recur(i);
}

기타 1개부터 모든기타를 사용하는 경우의 조합을 모두 찾기위해 recur()를 여러번 반복한다.

---

const recur = (end, start = 0, arr = [], sum = 0n) => {
  if (sum > 0) {
    const songCnt = sum.toString(2).match(/1/gi).length;
    const guitarCnt = arr.length;

    if (songCnt > songNum || (songCnt === songNum && guitarCnt < guitarNum)) {
      songNum = songCnt;
      guitarNum = guitarCnt;
    }
  }
  if (arr.length === end) {
    return;
  }

  for (let i = start; i < N; i++) {
    recur(end, i + 1, [...arr, i], sum | guitars[i]);
  }
};

이 recur()의 내부를 보면

for (let i = start; i < N; i++) {
    recur(end, i + 1, [...arr, i], sum | guitars[i]);
  }

start에 i+1을 넣어줌으로써 1,2 2,1과 같은 경우는 제외한다.
그리고 sum에 현재 sum과 탐색중인 guitar의 비트를 or연산한 결과를 넣어준다.
arr에는 기타를 어떤 순서로 골랐는지를 넣어뒀는데 이 순서는 중요하지 않다.

if (sum > 0) {
    const songCnt = sum.toString(2).match(/1/gi).length;
    const guitarCnt = arr.length;

    if (songCnt > songNum || (songCnt === songNum && guitarCnt < guitarNum)) {
      songNum = songCnt;
      guitarNum = guitarCnt;
    }
  }

이부분이 가장 중요한데 현재 비트연산 결과에서 1의 개수를 songCnt에 넣는다.
그리고 숫자의 조합개수는 guitarCnt에 넣는다.

만약 이전의 음악개수 > 현재구한 음악개수 일경우 혹은
음악개수 == 현재구한 음악갯수 && 이전의 기타개수 < 현재구한 기타개수 일경우
songNum과 guitarNum을 갱신해준다.

---

그러고서 guitarNum을 출력해주면 결과가 나오게된다.