[백준] 16938 캠프 준비 (Javascript)

문제

BOJ16938_캠프 준비

코드

// L <= 난이도의 총합 <= R
// 가장 어려운 문제의 난이도 - 가장 쉬운 문제의 난이도 >= X
const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, L, R, X] = input[0].split(' ').map(Number);
const difficulty = input[1].split(' ').map(Number);
let answer = 0;

backtracking(-1, 0, []);

console.log(answer);
function backtracking(cur, sum, stack) {
  	// 난이도의 합이 R을 초과할 경우 종료
    if (sum > R) return;
  	// 난이도 조건을 충족할 경우
    if (L <= sum && sum <= R && Math.max(...stack) - Math.min(...stack) >= X) answer++;
    for (let i = cur + 1; i < N; i++) {
        backtracking(i, difficulty[i] + sum, [...stack, difficulty[i]]);
    }
}

코드 설명

해당 문제의 제한 조건을 보면 N<=15이니 백트래킹을 통해 모든 경우의 수를 확인해서 풀 수 있다.
dfs()함수에 전달되는 매개변수들은 아래와 같다.

• cur : 현재 인덱스.
• sum : 난이도의 총합.
• stack : 현재 까지 방문한 문제들의 난이도가 배열 형태로 전달된다.

1. if (sum > R) return;
   현재까지 방문한 문제들의 난이도 총합이 R을 초과할 경우 더 이상 더해도 의미가 없으므로 현재 함수를 종료시킨다.
   

2. if (L <= sum && sum <= R && Math.max(...stack) - Math.min(...stack) >= X) answer++;
   난이도의 조건을 충족할 경우 정답 카운트를 1증가시킨다.

3. for (let i = cur + 1; i < N; i++) { ... }
   i를 cur+1로 초기화 하여 그 다음문제부터 탐색하도록 한다.