알고리즘 - 완전탐색 - 숫자 조합 2

최초 23/12/07

https://school.programmers.co.kr/learn/courses/30/lessons/87946

문제 요약

각 던전의 필요 체력와 소모 체력이 배열로 주어짐
ex) {{80,20}, {50,40}, {30,10}}
현재 체력과 각 던전의 필요 체력, 소모 체력이 주어질 때 최대 몇개의 던전을 돌 수 있는지 찾기
ex) 80, {{80,20}, {50,40}, {30,10}} > 80, 60, 50, 10 > 3

준비물

자료형 관련: int[][], ArrayList<int[]>, ArrayList.size(), ArrayList.add(), ArrayList.remove(), HashSet.add()
복사 관련: deep copy
알고리즘 관련: recursive 함수, permutation 구현 경험
디버깅 관련: 메모장에 예제 쓰는 습관

구현

import java.util.Set;
import java.util.List;
import java.util.HashSet;
import java.util.ArrayList;

class Solution {
    private Set<Integer> nums = new HashSet<>();
    
    public int solution(int k, int[][] dungeons) {
        List<Integer[]> dungeonList = new ArrayList<>();
        for (int[] dungeon : dungeons) {
            Integer[] tmp = new Integer[2];
            tmp[0] = dungeon[0];
            tmp[1] = dungeon[1];
            dungeonList.add(tmp);
        }
        
        explore(k, dungeonList, dungeonList.size());
        
        int max = 0;
        for (Integer num : nums) {
            if (num > max) {
                max = num;
            }
        }
        return max;
    }
    
    private void explore(int k, List<Integer[]> dungeonList, int length) {
        int available = 0;
        for (Integer[] dungeon : dungeonList) {
            if (k >= dungeon[0]) {
                available++;
            }
        }
        
        if (available == 0) {
            nums.add(length - dungeonList.size());
            return;
        }
        
        for (Integer[] dungeon : dungeonList) {
            if (k < dungeon[0]) {
                continue;
            }
            List<Integer[]> newList = new ArrayList<>(dungeonList);
            newList.remove(dungeon);
            explore(k - dungeon[1], newList, length);
        }
    }
}