백준 30959 앙상블할래?

문제

브루트포스 문제이다. 모든 조합을 대조해보고 만약에 하나만 골랐을 때 가장 확률이 높은 경우와 비교하여 다른 1개보다 많은 조합들의 확률이 더 높은 경우가 있을 때 1을 출력하고, 아니면 0을 출력하면 된다.

처음에는 모든 경우를 구하면서 2개씩 뽑으니까 2개씩 백트래킹 하면 되겠다고 생각해서 코드를 작성했다.

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const [a, ans, ...rest] = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
 
const [n, m] = a.split(" ").map(Number);
const answer = ans.split(" ").map(Number);
const predicts = rest.map((r) => r.split(" ").map(Number));
const visited = new Array(n).fill(false);
 
let result1 = -Infinity;
let resultOther = -Infinity;
 
function backTrack(combs) {
  const predict = new Array(m).fill(0);
  let good = 0;
 
  for (let i = 0; i < m; i++) {
    let c0 = 0;
    let c1 = 0;
    for (let j = 0; j < n; j++) {
      if (visited[j]) {
        predicts[j][i] ? c1++ : c0++;
      }
    }
    predict[i] = c0 > c1 ? 0 : 1;
    if (answer[i] === predict[i]) {
      good++;
    }
  }
 
  if (combs === 1) {
    result1 = Math.max(result1, good / m);
  } else if (combs % 2 === 1) {
    resultOther = Math.max(resultOther, good / m);
  }
 
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (!visited[j] && !visited[i]) {
        visited[i] = true;
        visited[j] = true;
        backTrack(combs + 2);
        visited[i] = false;
        visited[j] = false;
      }
    }
  }
}
 
for (let i = 0; i < n; i++) {
  visited[i] = true;
  backTrack(1);
  visited[i] = false;
}
 
console.log(result1 < resultOther ? 1 : 0);

띠용쓰? 하지만 시간초과가 떠버렸다 일단 다른 부분들을 다 고쳐봤지만 실질적인 문제를 해결하지는 못했다. 다른 방법으로는 하나씩 골랐을 때 가장 높은 정답률을 가지는 수를 미리 뽑고, 여기에 대해서 홀수개로 3개씩 조합을 골라 계산하다보면 결국 중간에 답이 나올 경우 시간을 더 쓰지 않고 빠져나올 수 있는 방식으로 바꾼 후 정답이 되었다.

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const [a, ans, ...rest] = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
 
const [n, m] = a.split(" ").map(Number);
const answer = ans.split(" ").map(Number);
const predicts = rest.map((r) => r.split(" ").map(Number));
const visited = new Array(n).fill(false);
 
const MAX_SINGLE = Math.max(
  ...predicts.map((model) =>
    model.reduce((sum, pred, i) => sum + (1 - (pred ^ answer[i])), 0)
  )
);
 
function backTrack(start, count) {
  let correct = 0;
  for (let i = 0; i < m; i++) {
    let ones = 0;
    let total = 0;
    for (let j = 0; j < n; j++) {
      if (visited[j]) {
        total++;
        if (predicts[j][i] === 1) ones++;
      }
    }
    const prediction = ones > total / 2 ? 1 : 0;
    if (prediction === answer[i]) correct++;
  }
 
  if (correct > MAX_SINGLE) {
    console.log(1);
    process.exit(0);
  }
 
  for (let i = start; i < n - 1; i++) {
    for (let j = i + 1; j < n; j++) {
      if (!visited[i] && !visited[j]) {
        visited[i] = true;
        visited[j] = true;
        backTrack(j + 1, count + 2);
        visited[i] = false;
        visited[j] = false;
      }
    }
  }
}
 
for (let i = 0; i < n; i++) {
  visited[i] = true;
  backTrack(i + 1, 1);
  visited[i] = false;
}
 
console.log(0);