백준 18223 < 러버덕을 사랑하는 모임 > JavaScript

📍문제 링크

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

18233번: 러버덕을 사랑하는 모임

 

📍알고리즘 분류

- 브루트포스

 

📍문제 풀이

(백트래킹) DFS를 활용해 nCp 조합을 구하고, 각 경우의 수가 범위를 만족하면서 전체 합이 E인 것을 구하면 된다

 

1. 조합을 구해야 하므로 백트래킹 코드를 만든다. 스택에는 실제 데이터가 아닌 인덱스만 담는 것이 간편하다

(중복을 제거하기 쉽고, 속도도 빠름)

 

2. p 가짓수를 뽑으면 브루트포스 검사를 실행할 check 함수를 실행한다

- check 함수에서 이 조합이 답이 될 수 있는 조합인지 판별한다

- 최솟값의 합 <= E <= 최댓값의 합 을 만족하면, 답이 되는 조합이다

 

📍코드 (JavaScript)

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];

rl.on("line", (line) => {
  input.push(line);
}).on("close", () => {
  const [N, P, E] = input.shift().split(" ").map(Number);
  const data = input.map((row) => row.split(" ").map(Number));
  const stack = []; // 0 ~ N-1 까지의 인덱스를 저장
  const isUsed = [];

  dfs(0);
  console.log(-1);

  function check() {
    // 사용할 인덱스에는 숫자를 채워서 마지막에 리턴할 배열
    const answer = Array(N).fill(0);
    let left = 0, right = 0;
    for (const idx of stack) {
      left += answer[idx] = data[idx][0];
      right += data[idx][1];
    }
    if (left <= E && E <= right) {
      // 답이 될 수 있는 경우 일단 N까지 순회
      for (let i = 0; i < N; i++) {
        // 답을 구성하는 학생이면
        if (answer[i]) {
          const gap = data[i][1] - data[i][0];
          if (left + gap < E) {
            left += gap;
            answer[i] += gap;
          } else {
            // left + gap >= E 이면 여기서 종료 가능
            answer[i] += E - left;
            console.log(answer.join(" "));
            process.exit();
          }
        }
      }
    }
  }

  function dfs(depth) {
    if (depth === P) {
      check();
      return; // 리턴하여 나머지 케이스 진행을 차단
    }
    for (let i = 1; i <= N; i++) {
      if (!isUsed[i]) {
        if (depth >= 1 && stack[depth - 1] > i - 1) continue;
        stack[depth] = i - 1;
        isUsed[i] = true;
        dfs(depth + 1);
        isUsed[i] = false;
      }
    }
  }
});