[JAVA] 프로그래머스 피로도_브루트포스

 

문제 : 

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

프로그래머스

 

 

접근 : 

 

 - 던전을 순서를 고려하면서 중복을 허용하지 않는 모든 경우의 수에 대해서 결과값을 도출한다.

 

 - EX 던전의 수가 3인경우

 

         1  2  3

         1  3  2

         2  1  3

         2  3  1

         3  1  2

         3  2  1

 

 - 만약 결과 값 중 던전의 수와 동일한 경우가 나오면 더 이상의 탐색하지 않는다. 

 

 

코드 구현 : 

 

class Solution {
    private int[][] dungeons;
    private boolean[] visited;
    private int ans;

    private void dfs(int stamina, int now, int count){
        if(ans == dungeons.length) return;
        
        for(int i = 0 ; i < dungeons.length ; i++){
            if(visited[i]) continue;
            if(stamina < dungeons[i][0]) continue;
            visited[i] = true;

            dfs(stamina - dungeons[i][1], now+1, count+1);
            visited[i] = false;
        }
        ans = Math.max(ans, count);
    }
    
    public int solution(int k, int[][] dungeons) {
        this.dungeons = dungeons;
        ans = 0;
        visited = new boolean[dungeons.length+1];

        dfs(k, 0, 0);
        return ans;
    }
}