문제

Programmers, 피로도

핵심

• 입력의 크기가 $8$이라 구현에 초점을 맞춘다.
• 초기 피로도, 던전의 개수, 던전을 돌기 위한 최소 피로도가 주어진다. 유저가 탐험할 수 있는 최대 던전 수를 구해야한다. 해당 문제는 완전 탐색 문제로 dfs를 이용해 1개 이상 던전을 돌았을 때마다 현재까지 탐험한 던전수를 갱신하면 된다. 중복해서 던전을 탐험할 수 없으므로 isSelected 배열을 이용해 중복을 체크한다. 또한 최소 피로도를 충족하지 못한 경우도 고려해야 한다. 던전의 총 개수를 재귀 함수의 종료조건으로 하여 코드로 나타내면 다음과 같다.

void dfs(int depth, int k, int mx, vector<bool>& isSelected, vector<vector<int>>& dungeons) {
    if (depth > 0) {
        answer = max(answer, depth);
        if (depth == mx) 
            return ;
    }
    for (int i = 0; i < dungeons.size(); ++i) {
        if (isSelected[i] || dungeons[i][0] > k)
            continue;
        isSelected[i] = true;
        dfs(depth + 1, k - dungeons[i][1], mx, isSelected, dungeons);
        isSelected[i] = false;
    }
}

개선

코드

시간복잡도

• 순서가 중요하므로 $O(n!)$

C++

#include <string>
#include <vector>
using namespace std;

int answer = -1;
void dfs(int depth, int k, int mx, vector<bool>& isSelected, vector<vector<int>>& dungeons) {
    if (depth > 0) {
        answer = max(answer, depth);
        if (depth == mx) 
            return ;
    }
    for (int i = 0; i < dungeons.size(); ++i) {
        if (isSelected[i] || dungeons[i][0] > k)
            continue;
        isSelected[i] = true;
        dfs(depth + 1, k - dungeons[i][1], mx, isSelected, dungeons);
        isSelected[i] = false;
    }
}

int solution(int k, vector<vector<int>> dungeons) {
    vector<bool> isSelected(dungeons.size(), false);
    dfs(0, k, dungeons.size(), isSelected, dungeons);
    return answer;
}

Java

class Solution {
    private int answer = -1;
    private void dfs(int depth, int k, int mx, boolean[] isSelected, int[][] dungeons) {
        if (depth > 0) {
            answer = Math.max(answer, depth);
            if (depth == mx)
                return;
        }
        for (int i = 0; i < dungeons.length; ++i) {
            if (isSelected[i] || dungeons[i][0] > k)
                continue;
            isSelected[i] = true;
            dfs(depth + 1, k - dungeons[i][1], mx, isSelected, dungeons);
            isSelected[i] = false;
        }
    }
    public int solution(int k, int[][] dungeons) {
        boolean[] isSelected = new boolean[dungeons.length];
        dfs(0, k, dungeons.length, isSelected, dungeons);
        return answer;
    }
}