피로도

ㅇ 문제

처음에 조건보고 너무쉽네ㅋㅋ 하고 자세히 보니, 모든 경우의수를 돌아봐야겠다 싶어서 절망했다..

일단 조건은 dungeons를 쭉 순회할때, dungeons의 행이 k 이하일때, k - 열을 해주고 cnt++ 해준다.

그럼 끝인데, 문제는 모든 경우의수를 어떻게 만드냐가 관건이었다.

그래서 그냥 모든걸 메서드로 만들기로 생각하고 순열을 만드는 메서드를 만들어 재귀로 풀었다.(사실 구글링함)

ㅇ 내풀이

//저장한 permutation 을 불러온다.
    //각 순열에서 maxTry를 해서 answer에 저장하고 전에 저장한 answer보다 크면 answer에 저장.
    public static int solution(int k, int[][] dungeons) {
        int answer = 0;

        List<int[]> permutations = generatePermutations(dungeons);
        for (int[] permutation : permutations) {
            int[][] dun = new int[dungeons.length][2];
            for (int i = 0; i < permutation.length; i++) {
                int dataIndex = permutation[i];
                dun[i][0] = dungeons[dataIndex][0];
                dun[i][1] = dungeons[dataIndex][1];
            }
            if(answer <= maxTry(dun,k)){
                answer = maxTry(dun,k);
            }
        }

        return answer;
    }
    //이 메서드는 각 경우의수에서 조건을 달아 정답을 반환함
    //조건 = 각 경우의수를 순회하며 k가 행 이상일때, k-열 해주고 cnt++. 만약 k가 행 미만일때는 그만
    //cnt 반환.
    public static int maxTry(int[][]dun,int k){
        int cnt = 0;
        for (int i = 0; i < dun.length; i++) {
            if (k >= dun[i][0]) {
                k -= dun[i][1];
                cnt++;
            }else{
                break;
            }
        }
        return cnt;
    }
    //주어진 arr 배열에서 모든 순열 만들고 저장
    public static List<int[]> generatePermutations(int[][] arr) {
        List<int[]> permutations = new ArrayList<>();
        int[] currentPermutation = new int[arr.length];
        boolean[] used = new boolean[arr.length];

        generatePermutations(arr, permutations, currentPermutation, used, 0);

        return permutations;
    }
    //파라미터 설명:
    //arr : 순열을 생성해야할 대상
    //permutations : 가능한 모든 순열을 저장하는 리스트
    //currentPermutation : 경우의수를만드는중 현재의 경우의수
    //used : 사용한 인덱스 추적
    //depth : 현재 생성중인 순열의 길이
    private static void generatePermutations(int[][] arr, List<int[]> permutations, int[] currentPermutation, boolean[] used, int depth) {
        //depth와 arr길이와 같으면 currentPermutation 은 하나의 순열이되어 permutation에 저장
        if (depth == arr.length) {
            permutations.add(currentPermutation.clone());
            return;
        }
        //0부터 arr길이까지 반복하며 사용되지 않은 인덱스를 찾고 찾으면 currentPermutation배열에 인덱스 추가하고 used업데이트하고
        //재귀호출해서 다음 순열 만든다.
        //재귀호출이 종료되면 해당 인덱스를 다시 사용하지않도록 used 배열 초기화한다.
        for (int i = 0; i < arr.length; i++) {
            if (!used[i]) {
                currentPermutation[depth] = i;
                used[i] = true;
                generatePermutations(arr, permutations, currentPermutation, used, depth + 1);
                used[i] = false;
            }
        }
    }

이렇게 보니 엄청 쓸데없이 길다. 다른분들의 풀이를 보자.

ㅇ 다른분들의 풀이

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);
    }
}

아닛; 이건 너무한거 아니냐고~

재귀로 이렇게 쉽게 푸는사람도 있다. 정말 허무하다!

내가 푼 방법보다 100배는 좋아보인다.

이 방법을 숙지해둬야겠다. 진심으로!