99클럽 코테 스터디 22일차 TIL 완전탐색(피로도)

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

프로그래머스

 

<아이디어>

현재 피로도로 탐험할 수 있는 최대 던전 수를 구하는 문제.

어떤 '순서'로 탐험하느냐에 따라 최대 던전 수가 달라진다. 범위가 크지 않은 것을 참고하여 순열로 구현했다.

1. 탐험할 던전의 순서를 순열로 정한다.

2. 현재 던전 순서에 따라 탐험 가능한 던전 수(cnt)를 구하고, 이때 마다 최댓값(answer)으로 갱신한다.

3. 모든 경우를 구하고 정해진 최댓값을 반환한다.

 

<제출코드>

import java.util.*;

class Solution {
    
    static int answer;
    static int len;
    static boolean[] select;
    
    // 순서대로 탐험했을 때 탐험 가능한 던전 수 계산하는 메서드
    public static void calc(int[] input, int k, int[][] dungeons){
        int cnt = 0;
        for(int i=0; i<len; i++){
            int d = input[i];
            // 현재 피로도보다 최소 필요 피로도가 작아야 함
            if(k < dungeons[d][0]) continue;
            k -= dungeons[d][1];
            cnt++;
        }
        answer = Math.max(answer, cnt);
    }
    
    // 탐험할 던전의 순서 정하는 메서드
    public static void permu(int cnt, int[] input, int k, int[][] dungeons){
        if(cnt == len){
            calc(input, k, dungeons);
            return;
        }
        for(int i=0; i<len; i++){
            if(select[i]) continue;
            input[cnt] = i;
            select[i] = true;
            permu(cnt+1, input, k, dungeons);
            select[i] = false;
        }
    }
    
    public int solution(int k, int[][] dungeons) {
        
        len = dungeons.length;
        int[] input = new int[len];
        select = new boolean[len];
        permu(0, input, k, dungeons);
        
        return answer;
    }
}