피로도

 

 

 

 

import java.util.*;

class Solution {
    
    static boolean visit[];
    static int max;
    
    public int solution(int k, int[][] dungeons) {
        
        int answer = -1;
        max = Integer.MIN_VALUE;
        
        visit = new boolean[dungeons.length];
        
        // 탐험을 시작하는 함수 호출 (초기 탐험 횟수는 0)
        solve(k,dungeons, 0);
        answer = max;
        
        return answer;
        
    }
    
    
    
    public static void solve(int k, int[][] dungeons, int count ) {
           
         // 최대 탐험 횟수 갱신 (현재까지 탐험한 횟수와 비교하여 최대값을 갱신)
        max = Math.max(max,count);          
        
        for(int i=0; i<dungeons.length; i++) {
            
             // 아직 방문하지 않은 던전이고, 현재 피로도가 던전의 최소 피로도보다 큰 경우
            if(!visit[i] && dungeons[i][0]<=k) {
                
                visit[i] = true;
                
                // 던전 탐험 후 남은 피로도로 재귀 호출
                solve(k-dungeons[i][1], dungeons, count+1);
                visit[i] = false;
                
                
            }
        
        
    }
}
}