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

https://programmers.co.kr/learn/courses/30/lessons/87946

코딩테스트 연습 - 피로도

 

저는 순열을 통해 해당 문제를 해결하였습니다.

dungeons의 개수가 8이하여서 순열로 풀어도 8!이므로 1초안에 들어갈 것이라 생각하였습니다.

 

package Programmers.ETC;

public class 피로도 {
    public int solution(int k, int[][] dungeons) {
        int answer = -1;
        boolean[] used = new boolean[dungeons.length];
        answer = dfs(0,k,used,dungeons);
        return answer;
    }
    private static final int NEED_FATIGUE = 0;
    private static final int FATIGUE = 1;//fatigue
    private int dfs(int depth,int k , boolean[] used,int[][] dungeons){
        if(depth == dungeons.length){
            return 0;
        }
        int result = 0;
        for(int i = 0 ; i < dungeons.length ; i++){
            if(used[i]){
                continue;
            }
            if(k < dungeons[i][NEED_FATIGUE]){
                continue;
            }
            used[i] = true;
            result = Math.max(result,dfs(depth+1,k-dungeons[i][FATIGUE],used,dungeons)+1);
            used[i] = false;
        }
        return result;
    }
}