[백준/node.js] 18429번 근손실

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

18429번: 근손실

 

문제 분석

분류

백트래킹, DFS

문제 설명

웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 다행히도 이 대학원생은 N개의 서로 다른 운동 키트를 가지고 있다. 이 대학원생은 하루에 1개씩의 키트를 사용하며, 매일 어떤 키트를 사용할지 마음대로 결정할 수 있다.

N개의 운동 키트에 대한 정보가 주어졌을 때, N일간 하루에 1개씩의 운동 키트를 사용하는 모든 경우 중에서, 운동 기간동안 항상 중량이 500 이상이 되도록 하는 경우의 수를 출력해 보자.​

입력

첫째 줄에 자연수 N과 K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 8, 1 ≤ K ≤ 50)
둘째 줄에 각 운동 키트의 중량 증가량 A가 공백을 기준으로 구분되어 주어진다. (1 ≤ A ≤ 50)

출력

N일 동안 N개의 운동 키트를 사용하는 모든 경우 중에서, 운동 기간 동안 항상 중량이 500 이상이 되도록 하는 경우의 수를 출력한다.

 

소스코드

const [n, k, ...arr] = require("fs").readFileSync("/dev/stdin").toString().trim().split(/\s/);
const N = Number(n);
const K = Number(k);
const kit = arr.map(Number);

let visit = Array.from({length: N}, _ => false);
let result = 0;

function dfs(day, weight){
    if(weight < 0) {
        return;
    }
    
    if(day === N) {
        result = result + 1;
        return;
    }
    
    for(let i = 0; i < N; i++){
        if (visit[i] === true) continue;
        visit[i] = true;
        dfs(day + 1, weight + kit[i] - K);
        visit[i] = false;
    }
}

dfs(0, 0);
console.log(result);

 

문제풀이

const [n, k, ...arr] = require("fs").readFileSync("/dev/stdin").toString().trim().split(/\s/);
const N = Number(n);
const K = Number(k);
const kit = arr.map(Number);

운동 키트의 개수와 운동 기간을 나타내는 N을 입력받고, 하루마다 감소하는 중량인 K를 입력받는다.
node.js로 입력받을 때, String으로 저장되기 때문에 계산을 위해서 Number로 바꾸어준다.
각 운동 키트의 중량 증가량은 kit에 입력받는다. 마찬가지로 map을 사용해서 Number로 바꾸어준다.

let visit = Array.from({length: N}, _ => false);
let result = 0;

각 운동 키트는 한 번씩 사용할 수 있기 때문에 visit로 사용여부를 판단한다.
경우의 수를 저장할 수 있는 result를 0으로 초기화해 둔다.

function dfs(day, weight){
    if(weight < 0) {
        return;
    }
    
    if(day === N) {
        result = result + 1;
        return;
    }
    
    for(let i = 0; i < N; i++){
        if (visit[i] === true) continue;
        visit[i] = true;
        dfs(day + 1, weight + kit[i] - K);
        visit[i] = false;
    }
}

깊이 우선 탐색으로 근손실 여부를 구해보자. 필요한 것은 1. 파라미터 2. 탈출 조건 3. return문이다.
1. 파라미터로는 현재 날짜를 day로 현재 무게를 weight로 설정했다.
2. for문의 범위가 끝났거나 이미 방문했을 때에 재귀의 탈출할 수 있다.
3. 첫 번째 return문은 무게가 마이너스여서 근손실이 발생한 경우이고, 
    두 번째 return문은 근손실이 발생하지 않았고, 날짜가 모두 지난 경우이다.

dfs(0, 0);
console.log(result)

완성된 dfs함수를 초기값으로 실행하고, result값을 출력하면 끝나게 된다.