[자바] 프로그래머스 - 피로도 (Level2)

🔗 문제 링크

코딩테스트 연습 - 피로도

📝 문제 설명

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.

 

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러 개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전 별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할 수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

⚠️ 제한사항

• k는 1 이상 5,000 이하인 자연수입니다.
• dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
  • dungeons의 가로(열) 길이는 2 입니다.
  • dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"]입니다.
  • "최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
  • "최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
  • 서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.

🖨 입출력 예

k	dungeons	result
80	[[80,20],[50,40],[30,10]]	3

📂 분류

완전 탐색, 순열, DFS, 시물레이션

💡 풀이

이 문제는 던전의 개수가 최대 8개이다. 즉, 최대 경우의 수가 8! 이기 때문에 순열을 구해 완전 탐색을 하면 해결할 수 있는 문제다.

 

c++에서는 순열 라이브러리를 제공했는데 java에서는 순열 라이브러리를 제공하지 않아서 직접 구현해야 했다.

💻 코드

import java.util.*;

class Solution {
    private class Fatigue {
        private int minimumFatigue;
        private int consumeFatigue;

        Fatigue(int mf,  int cf) {
            this.consumeFatigue = cf;
            this.minimumFatigue = mf;
        }
    }

    private static ArrayList<Fatigue> fatigues = new ArrayList<>();
    private boolean[] visited;
    private int[] orderOfExploration;
    private int answer = 0;

    public int solution(int k, int[][] dungeons) {
        initialize(dungeons);
        permutation(0, k, dungeons.length);
        return answer;
    }

    void initialize(int[][] dungeons) {
        visited = new boolean[dungeons.length];
        orderOfExploration = new int[dungeons.length];
        for (int[] d : dungeons) {
            fatigues.add(new Fatigue(d[0], d[1]));
        }
    }

    void permutation(int depth, int k, int n) {
       if (depth == n) {
           answer = Math.max(answer, executeSimulation(k));
           return;
       }

       for (int i = 0; i < n; i++) {
           if (!visited[i]) {
               visited[i] = true;
               orderOfExploration[depth] = i;
               permutation(depth + 1, k, n);
               visited[i] = false;
           }
       }
    }

    int executeSimulation(int k) {
        int ret = 0;
        for (int d : orderOfExploration) {
            Fatigue f = fatigues.get(d);
            if (k >= f.minimumFatigue) {
                k -= f.consumeFatigue;
                ret += 1;
            }
        }
        return ret;
    }
}