프로그래머스 피로도 java

문제링크

문제 접근

• 소모 피로도로 정렬해서 순서대로 하면될까? -> 최소 필요 피로도에 대한 조건이 부족해서 안됨
• 주어진 예시에서도 사용된 피로도 순서가 20 -> 10 -> 40 으로 정렬기준 만족 X
• 던전 갯수가 최대 8이므로 완전탐색 ( 순열 )

코드

class Solution {
    static int n;
    static int piro;
    static boolean[] used;
    static int[] order;
    static int answer;
    public int solution(int k, int[][] dungeons) {
        n = dungeons.length;
        piro = k;
        used = new boolean[n];
        order = new int[n];
        
        perm(0,dungeons);
        return answer;
    }
    private static void perm(int idx, int[][] dungeons){
        if(idx == n){ // 순서 다 정해졌으니 돌면서 던전 갯수 카운트
            int cnt = 0;
            int nowP = piro;
            for(int i=0;i<n;i++){
                int nowOrder = order[i];
                if(dungeons[nowOrder][0] > nowP) break;
                else{
                    nowP -= dungeons[nowOrder][1];
                    cnt++;
                }
            }
            answer = Math.max(answer, cnt);
            return;
        }
        for(int i=0;i<n;i++){
            if(!used[i]){
                order[idx] = i;
                used[i] = true;
                perm(idx+1, dungeons);
                used[i] = false;
            }
        }
    }
}

결과

정리

• 순열, 조합 재귀 코드를 알차게 쓴다.