[JAVA] Programmers : 피로도

문제

코딩테스트 연습 - 피로도

 

해결방법

오랜만에 알고리즘 풀이를 들고 왔다.

사실 알고리즘은 꾸준히 풀고 있었는데 시간도 없고 귀찮아서 글은 쓰지 않고 있었다.

 

문제에 대해 이야기하자면 기본적인 순열 문제라고 볼 수 있다.

순열을 이용해서 던전의 모든 방문 순서를 찾고 해당 방문 순서에 몇 개의 던전이 탐색 가능한지 확인한다.

그다음 그중에서 가장 많은 던전을 방문한 횟수를 출력하면 된다.

 

코드

class Solution {
    static int[] result;
    static boolean[] visited;
    static int[][] dungeons;
    static int k;
    static int max = -1;
    
    public int solution(int k, int[][] dungeons) {
        int answer = -1;
        
        this.dungeons = dungeons;
        this.k = k;
        
        int length = dungeons.length;
        result = new int[length];
        visited = new boolean[length];
        
        permu(0, length);
        answer = max;
        
        return answer;
    }
    
    static void permu(int depth, int end) {
        if (depth >= end) {
            max = Math.max(max, goDungeons());
            return;
        }
        
        for (int i = 0; i < end; i++) {
            if (!visited[i]) {
                visited[i] = true;
                result[depth] = i;
                permu(depth + 1, end);
                visited[i] = false;
            }
        }
    }
    
    static int goDungeons() {
        int count = 0;
        int startPoint = k;
        for (int i = 0; i < result.length; i++) {
            if (dungeons[result[i]][0] <= startPoint) {
                startPoint -= dungeons[result[i]][1];
                count++;
            } else break;
        }
        return count;
    }
}