[ 프로그래머스 ] 87946 피로도

Link 프로그래머스 87946번 문제 : 피로도

📌 About

Dungeons의 길이가 8 이하이기 때문에 brute force으로 해결할 수 있다.

또한 던전의 탐험 여부를 백트래킹으로 변경해야 한다.

📌 Code

class Solution {
    public int solution(int k, int[][] dungeons) {
        return explore(dungeons, new boolean[dungeons.length], k, 0);
    }

    private int explore(int[][] dungeons, boolean[] explored, int fatigue, int exploration) {
        int maxExploration = exploration;
        for (int d = 0; d < dungeons.length; d++) {
            if (!explored[d] && fatigue >= dungeons[d][0]) {
                explored[d] = true;
                maxExploration = Math.max(maxExploration,
                        explore(dungeons, explored, fatigue - dungeons[d][1], exploration + 1));
                explored[d] = false;
            }
        }
        return maxExploration;
    }
}