[프로그래머스/Java] 피로도

🔗 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/87946

프로그래머스

 

🔍 해결 과정

dungeons의 최대 길이가 8이므로 완전 탐색을 활용하여 모든 순서에 대해서 탐험할 수 있는 던전의 최대 개수를 구하는 방법으로 코드를 구현하였습니다. 

 

시간 복잡도: O(n!) (n: 던전의 개수)

 

---

✏️ 코드

class Solution {
    
    public int solution(int k, int[][] dungeons) {
        return getResult(dungeons, new boolean[dungeons.length], k);
    }
    
    private int getResult(int[][] dungeons, boolean[] visited, int k) {
        int maxCount = 0;
        
        for (int i = 0; i < dungeons.length; ++i) {
            if (visited[i] || dungeons[i][0] > k) {
                continue;
            }
            
            visited[i] = true;
            maxCount = Math.max(maxCount, 1 + getResult(dungeons, visited, k - dungeons[i][1]));
            visited[i] = false;
        }
        
        return maxCount;
    }
}