(Java) 프로그래머스 피로도

문제를 읽자마자 완전탐색으로 구현해야 한다고 생각했다.

정렬을 해봐야 의미가 없고 던전의 개수도 8개 밖에 되지않아

완전탐색으로 충분히 해결할수 있을것 같다는 생각이 들었다.

Dfs를 이용해서 어렵지 않게 풀었다.

---

최종코드

    public int solution(int k, int[][] dungeons) {
    	// DFS를 위한 전역변수 설정
    	public static boolean[] visit;
    	public static int answer = 0;
        
        // 던전 개수만큼 visit 설정
        visit = new boolean[dungeons.length];
        // 최댓값을 위한 cnt
        int cnt = 0;
        DFS(k, dungeons, cnt);

        return answer;

    public static void DFS(int k, int[][] dungeons, int cnt) {
        for (int i = 0; i < dungeons.length; i++) {
            // visit[i]를 방문하지 않았고 피로도 조건이 맞으면
            if(!visit[i] && dungeons[i][0] <= k) {
                visit[i] = true;
                // 소모 피로도를 설정하고 재귀
                DFS(k - dungeons[i][1], dungeons, cnt+1);
                visit[i] = false;
            }
        }
        answer = Math.max(cnt, answer);
    }
}