피로도 [자바]

 

🧫 문제 분석

✔️ 출처

피로도 level 2

📖 문제

 

현재 피로도 k >= 최소 필요 피로도 인 조건을 따져서 백트래킹 완전탐색을 하면 된다. 

(최소 필요 피로도 >= 소모 피로도)

 

문제에서 던전 개수가 8 이하이기에 완전탐색을 해도 시간복잡도가 괜찮을 거 같다는 생각이 들었다. 

 

---

🔅 문제 풀이

import java.util.Arrays;

class Solution {
    // 현재 피로도 (k), [최소 필요 피로도, 소모 피로도]
    // 최필피 >= 소피
    boolean[] visited;
    int max = 0;
    
    public int solution(int k, int[][] dungeons) {        
        visited = new boolean[dungeons.length];
        dfs(k, dungeons, 0);
        return max;
    }
    
    private void dfs(int k, int[][] dungeons, int cnt) {
        for (int i = 0; i < dungeons.length; i++) {
            
            // 방문하지 않았고, 현재 피로도가 던전 최소 필요 피로도보다 같거나 클때
            if (!visited[i] && k >= dungeons[i][0]) {  
                visited[i] = true;
                dfs(k - dungeons[i][1], dungeons, cnt + 1);
                visited[i] = false;
            }
        }
        
        max = Math.max(cnt, max);
    }
    
}

 

❗ 오답노트 / 필요한 지식