Programmers - 피로도 (Java) 완전탐색

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

프로그래머스

---

[문제풀이] 

입력으로 들어오는 배열 길이가 최대 8이므로 완전탐색으로 해결 할 수 있습니다.

 

우선 저는 순열을 이용해 모든 경우의 수를 구하여 문제를 해결하였습니다.

 

class Solution {
    static int max = Integer.MIN_VALUE;

    public static int solution(int k, int[][] dungeons) {

        Solution.permutation(dungeons,0, dungeons.length,dungeons.length,k);

        return max;
    }


    static void permutation(int[][] arr, int depth, int n, int r, int k) {
        if (depth == r) {
            check(arr, r, k);
            return;
        }

        for (int i=depth; i<n; i++) {
            swap(arr, depth, i);
            permutation(arr, depth + 1, n, r,k);
            swap(arr, depth, i);
        }
    }

    static void swap(int[][] arr, int depth, int i) {
        int minimum = arr[depth][0];
        arr[depth][0] = arr[i][0];
        arr[i][0] = minimum;

        int need = arr[depth][1];
        arr[depth][1] = arr[i][1];
        arr[i][1] = need;

    }
    static void check(int[][] arr, int r, int userStamina) {

        int ableDungeons = 0;
        for (int i = 0; i < r; i++) {
            // System.out.print("["+arr[i][0] + "," + arr[i][1] + "] " );
            if(userStamina >= arr[i][0]){
                userStamina -= arr[i][1];
                ableDungeons++;
            }
        }//System.out.println();

        if(ableDungeons > max) max = ableDungeons;
    }

}

 

밑의 코드는 다른 분이 푸신 코드인데요,

dfs를 이용해 완전탐색을 해서 문제를 해결하셨습니다.

class Solution {
    public static boolean check[];
    public static int ans = 0;

    public int solution(int k, int[][] dungeons) {
        check = new boolean[dungeons.length];

        dfs(k, dungeons, 0);

        return ans;
    }
    public static void dfs(int tired, int[][] dungeons, int cnt){
        for(int i=0; i<dungeons.length; i++){
            if(!check[i] && dungeons[i][0]<=tired){
                check[i] = true;
                dfs(tired-dungeons[i][1], dungeons, cnt+1);
                check[i] = false;
            }
        }
        ans = Math.max(ans, cnt);
    }
}