완전탐색. 피로도

문제

[요구피로도, 소모피로도] 형태의 이차원 배열이 주어지고, 가지고있는 피로도가 주어진다.
돌수있는 최대 던전의 수를 구하는 문제다.

해결방향성

애초에 그리디로 풀수가 없다. 요구피로도에 따라 던전에 입장하면, 소모되는 피로도가 변동이 너무 크기 때문에 완전탐색을 선택했다. 1번만 방문할수있으므로, 중복 방문을 체크하고, 요구 피로도가 가지고있는 피로도보다 높은 던전만 탐색한다. 던전을 지날때마다 피로도를 깎고, 카운트를 늘린다. 그리고 모든 던전의 방문 여부를 체크하면, 돌수있는 던전의 카운트가 나오는데, 최대값을 저장해주면된다.

코드

public class Solution {
    static int max = 0;
    public int solution(int k, int[][] dungeons) {
        int totalCount = dungeons.length; // 총 던전의 개수

        // k는 가지고있는 피로도
        // 최소 피로도가 있어야 들어갈수있음. dungeons[i][0] == 최소 피로도 dungeons[i][1] == 소모 피로도

        boolean[] visited = new boolean[totalCount];
        DFS(dungeons, k, 0, visited, 0);

        return max;
    }

    private void DFS(int[][] dungeons, int k, int depth, boolean[] visited, int count) {
        for (int i = 0; i < dungeons.length; i++) {
            if (!visited[i] && dungeons[i][0] <= k) { // 피로도가 남음
                visited[i] = true;
                DFS(dungeons, k - dungeons[i][1], i, visited, count + 1); // 피로도 줄어듬, 던전수++
                visited[i] = false;
            }
        }
        max = Math.max(count, max);
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        int[][] dungeons = {{80, 20}, {50, 40}, {30, 10}};
        System.out.println(s.solution(70, dungeons));
    }
}

결론

DFS를 통한 완탐문제.