[프로그래머스] 피로도

문제

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

알고리즘

dfs

풀이

제한사항이 완전 탐색으로 풀어도 가능한 숫자이기 때문에 재귀함수 이용하여 전체 경우의 수를 다 탐색하고 가장 큰 수를 return 해주었다.

코드

class Solution {
    
    static int answer;
    static int[] check;
    public int solution(int k, int[][] dungeons) {
        answer = -1;
        check = new int[dungeons.length];

        dfs(0, k, dungeons);

        return answer;
    }

    private void dfs(int L, int k, int[][] dungeons) {
        for (int i = 0; i < dungeons.length; i++) {
            if (check[i] == 0 && k >= dungeons[i][0]) {
                check[i] = 1;
                dfs(L + 1, k - dungeons[i][1], dungeons);
                check[i] = 0;
            }

            answer = Math.max(answer, L);
        }
    }
}