[JS][백준]16938_캠프 준비

문제 번호

16938번: 캠프 준비

 

 

알고리즘 분류

• 수학
• 브루트포스 알고리즘
• 조합론
• 비트마스킹
• 백트래킹

 

문제 풀이

  주어진 N개의 문제들 중 2개 이상 N개 이하의 문제를 뽑는 경우를 생각해본다.

  for (let i = 2; i <= N; i++) {  // 몇 문제를 뽑을건인가.
    sol(i, 0, visited, 0, nums, 0);
  }

 

 i개의 문제를 모두 뽑았다면 문제에서 주어진 조건들을 만족하는지 확인해보자.

if (cnt === numOfProblems) {
    let temp = [...nums];
    temp.sort((a, b) => {
      if (a < b) return -1;
      else if (a > b) return 1;
      return 0;
    })
    if (L <= sum && sum <= R && temp[temp.length - 1] - temp[0] >= X) {  // 문제조건.
      return answer++;
    }
    return;
  }

 

아직 i개의 문제를 다 뽑지 못했다면 i개의 문제를 모두 뽑자.

else {
    for (let i = start; i < problems.length; i++) {
      if (!visited[i]) {
        visited[i] = true;
        sum += problems[i];
        nums.push(problems[i]);
        sol(numOfProblems, cnt + 1, visited, sum, nums, i + 1);
        visited[i] = false;
        sum -= problems[i];
        nums.pop();
      }
    }
  }

 

전체 코드

/**
 * 2~15개를 뽑는다. O ? 10^8?
 * 뽑으면서 Sum은 더하고, 뽑은 숫자는 배열에 넣어준다.
 */

const input = require('fs').readFileSync('dev/stdin').toString().trim().split('\n');
const [N, L, R, X] = input[0].split(' ').map(Number);  // 문제 수, 최소, 최대, 차이.
let problems = input[1].split(' ').map(Number);

let answer = 0;
function sol(numOfProblems, cnt, visited, sum, nums, start) {
  if (cnt === numOfProblems) {
    let temp = [...nums];
    temp.sort((a, b) => {
      if (a < b) return -1;
      else if (a > b) return 1;
      return 0;
    })
    if (L <= sum && sum <= R && temp[temp.length - 1] - temp[0] >= X) {  // 문제조건.
      return answer++;
    }
    return;
  } else {
    for (let i = start; i < problems.length; i++) {
      if (!visited[i]) {
        visited[i] = true;
        sum += problems[i];
        nums.push(problems[i]);
        sol(numOfProblems, cnt + 1, visited, sum, nums, i + 1);
        visited[i] = false;
        sum -= problems[i];
        nums.pop();
      }
    }
  }  
}
function main() {
  let visited = new Array(N).fill(false);
  let nums = [];
  for (let i = 2; i <= N; i++) {  // 몇 문제를 뽑을건인가.
    sol(i, 0, visited, 0, nums, 0);
  }
  return console.log(answer);
}
main();

특이사항

 매개변수로 받은 배열을 정렬하면 함수가 호출된 시점으로 돌아가도 해당 배열은 정렬되어있다.

[Javascript] 자바스크립트에서 매개변수(parameter) 할당