プログラマーレベル2|疲労JS

疲労度
問題の説明
XXゲームには疲労度システム(0以上の整数で表示)があり、一定の疲労度探索コピーを使用できます.このとき,各レプリカには,探検開始に必要な「最小必要疲労度」と,レプリカ探検完了時に消費される「消費疲労度」がある.「最小必要疲労度」は、探検コピーに必要な最小疲労度を表し、「疲労度の消費」は、探検コピー後に消費される疲労度を表します.例えば、「最小需要疲労度」が80、「消耗疲労度」が20のコピーを探索するためには、プレイヤーの現在の残りの疲労度は80以上でなければならず、探検コピー後は20の疲労度を消費する.
このゲームには1日に1回探検できるコピーが複数あり、1人のプレイヤーが今日のコピーをできるだけ多く探検したいと思っています.プレイヤーの現在の疲労度kと各レプリカの「最小必要疲労度」、「消耗疲労度」の2次元配列がパラメータとしてしっかり与えられている場合は、解題関数を完了し、プレイヤーが探検できる最大レプリカ数を返してください.
せいげんじょうけん

kは1以上5000以下の自然数です.

刑務所の長手方向(行)の長さ(すなわち、コピーの個数)は1または8未満である.

地牢の横方向(列)の長さは2である.

刑務所の各行は、各コピーの[「最小必要疲労度」「消費疲労度]]である.

「最低必要疲労度」は、常に「消費疲労度」以上である.

「最低必要疲労度」と「消費疲労度」は1以上1000以下の自然数です.

の異なるコピーの［「最小必要疲労度」、［消費疲労度］は同じである可能性があります.

I/O例
kdungeonsresult80[[80,20],[50,40],[30,10]]3
I/O例説明
今の疲労度は80です.
1つ目→2つ目→3つ目のコピーの順に探検すると

現在の疲労度は80です.また、最初のコピーを検索することもできます.このコピーには「必要最小限の疲労度」が80である必要があります.最初のコピーの「消耗疲労度」は20で、探検コピー後の残りの疲労度は60です.

残りの疲労度は60で、2番目のコピーを回すのに必要な「最小必要疲労度」は50で、2番目のコピーを探検することができます.2番目のコピーの「消耗疲労度」は40で、探検コピー後の残りの疲労度は20です.

残りの疲労度は20で、3番目のコピーを転送するために必要な「最小必要疲労度」は30です.そのため、3番目のコピーは探検できません.

1つ目→3つ目→2つ目のレプリカの順に探検すると

現在の疲労度は80です.また、最初のコピーを検索することもできます.このコピーには「必要最小限の疲労度」が80である必要があります.最初のコピーの「消耗疲労度」は20で、探検コピー後の残りの疲労度は60です.

残りの疲労度は60で、3番目のコピーを回すのに必要な「最小必要疲労度」は30で、3番目のコピーを探検することができます.3つ目のコピーの「消耗疲労度」は10で、探検コピー後の残りの疲労度は50です.

残りの疲労度は50で、2番目のコピーを回すのに必要な「最小必要疲労度」は50で、2番目のコピーを探検することができます.2番目のコピーの「消耗疲労度」は40で、探検コピー後の残りの疲労度は10です.
したがって,この場合3つのコピーを探検することができ,プレイヤーが探検できる最大コピー数は3である.

function solution(k, dungeons) {
    const len = dungeons.length;
    //모든 경우의 수를 확인하기 위한 배열
    const visited = new Array(len).fill(false);
    //클리어 횟수를 확인
    let clearCnt = 0;
    
    //모든 경우의 수를 확인하기 위한 재귀
    const dfs = (k, curCnt) => {
      	//현재 클리어 횟수와 전의 클리어 횟수를 비교
        clearCnt = Math.max(curCnt, clearCnt);
      
        for(let i=0; i<len; i++) {
            const [minK, useK] = dungeons[i];
            
            //현재 피로도보다 크고 확인한적이 없다면            
            if(k >= minK && !visited[i]) {
                //확인, 피로도 감소 및 카운트 증가 후 재귀  
                visited[i] = true;
                dfs(k - useK, curCnt + 1);
                visited[i] = false;
            }
        }
    }
    dfs(k, 0);
    
    return clearCnt;
}