[Programmers] 87946. 피로도 (java)

https://school.programmers.co.kr/learn/courses/30/lessons/87946?language=java  

 

문제 파악

유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return하기

 

 

문제 풀이

📌 완전탐색

• 백트래킹을 사용하여 던전을 탐험할 수 있는 모든 순서를 살펴보고, 가능한 최선의 결과를 도출한다.

백트래킹

class Solution {
    static int ans = 0;
    
    public int solution(int k, int[][] dungeons) {
        backtracking(new boolean[dungeons.length], 0, k, dungeons);
        return ans;
    }
    
    void backtracking(boolean[] visited, int curr, int k, int[][] dungeons) {
        if (curr > ans) 
            ans = curr;
        
        for (int i = 0; i < dungeons.length; i++) {
            if (visited[i] || k < dungeons[i][0]) continue;
            
            visited[i] = true;
            backtracking(visited, curr + 1, k - dungeons[i][1], dungeons);
            visited[i] = false;
        }
    }
}

📊 실행 결과

 

 

NOTE

✅ "재귀 고려해서 count 업데이트하는 구현" 반복 연습 필요