[프로그래머스] 피로도(JAVA)

코딩테스트 연습(완전탐색) - 피로도

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

프로그래머스

문제 설명

던전을 탐색하기 위해선 최소한으로 가지고있어야하는 피로도가 있고 그에 따라 소모되는 피로도가 따로 있다.

던전을 최대한 많이 탐색하려고 했을 때 몇개의 던전을 탐색할 수 있는 지 구하는 문제이다.

입력값은 현재 남아있는 피로도와 각 던전의 "최소요구 피로도", "소모 피로도"가 주어진다.

---

문제 풀이

생각 과정

사실 완전탐색 카테고리에 있는 문제여서 바로 완전탐색으로 생각하긴 했다.

근거를 다시 찾아보면 던전의 개수가 8개로 매우작다. 탐색하는 개수가 8!개 이므로 완전탐색으로 충분히 풀 수 있는 범위이다.

구현

public class 완전탐색_피로도 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int k = 80;
        int[][] d  ={{80,20},{50,40},{30,10}};
        System.out.println(solution.solution(k, d));
    }

    static boolean[] visit;	// 중복방지를 위한 배열
    static int max;	// 결과값을 저장할 변수
    static class Solution {
        public int solution(int k, int[][] dungeons) {
            int len = dungeons.length;
            visit = new boolean[len];
            dfs(dungeons,0,k);
            return max;
        }

        private void dfs(int[][] dungeons, int cnt, int p) {
            max = Math.max(max, cnt);	// 성공적으로 던전에 들어왔다면 최댓값 갱신

            for (int i = 0; i < len; i++) {
                int needP = dungeons[i][0], consumeP = dungeons[i][1];
                if (visit[i] ||p<needP) continue;	// 방문했던 곳이거나 최소 피로도보다 낮다면
                visit[i] = true;
                dfs(dungeons, cnt + 1, p-consumeP);
                visit[i] = false;
            }
        }
    }
}