프로그래머스 - 피로도

이 문제에서 중요한 부분은, 언뜻보면 그리디 문제로 생각하기 쉽다는 것이다. 그런데 아래 주석에도 있듯이 잘 (생각해)보면 결국 완전탐색이 필요하다. 그 이후로는 백트래킹을 이용해 그냥 잘 구현하면 된다. (던전을 순서대로 나열하는 모든 경우의 수를 구해야 하므로)
이하 코드 참고

class Solution {
    static int[][] arr;
    static int[] sunseo;
    static int[] isUsed;
    static int health;
    static int answer = 0;
    public int solution(int k, int[][] dungeons) {
        //문제
        //현재 피로도
        //각 던전(최소 필요 필로도, 소모 피로도)
        //최대한 많이 도는 수
        //풀이
        //최대한 많이 돌아봐야 하므로, 일단 소모 피로도가 적은 순으로
        //그다음 최소 필요 피로도 순으로 보려는데 이러면 의미가 없음
        //그냥 다 해봐야 함
        health = k;
        arr = dungeons;
        sunseo = new int[dungeons.length];
        isUsed = new int[dungeons.length];
        bt(0);
        return answer;
    }
    static void bt(int index){
        if(index == sunseo.length){
            //피로도를 사용하여 돌 수 있는 던전 갯수
            //if(갯수 > answer) answer = 갯수
            //현재 순서대로 던전들 돌기
            //던전돌기전, 
            //if(현재피로도 < 필요최소피로도 계속) 멈추고 돌은 던전 갯수++
            //던전돌은후, 현재피로도-소모피로도, 돌은 던전 갯수++
            int n = 0; //돌은 던전 갯수
            int h = health; //현재 남은 체력
            for(int i = 0; i < sunseo.length; i++){
            	//현재 돌 던전
                int now = sunseo[i];
                //던전의 필요최소피로도가 현재체력보다 크면
                if(arr[now][0] > h){
                    if(n > answer){
                        answer = n;
                    }
                    break;
                }
                //던전을 돌고난 후
                h -= arr[now][1];
                n++;
            }
            //모든 던전을 다 돌았을 경우
            if(n > answer){
                answer = n;
            }
            return;
        }
        for(int i = 0; i < sunseo.length; i++){
            if(isUsed[i] == 1){
                continue;
            }
            sunseo[index] = i;
            isUsed[i] = 1;
            bt(index+1);
            isUsed[i] = 0;
        }
    }
}