[Programmers/C++] 피로도

시간 복잡도

• 던전의 개수가 최대 8이므로 $O(n!)$ 이므로 시간은 충분합니다.

문제 접근법

• 들어갈 수 있는 던전에 대한 모든 경우의 수를 구합니다.
• 탐험할 던전의 최소 필요 피로도보다 현재 피로도가 낮으면 탐험하지 않습니다.
• DFS 수행이 끝난 후 다른 경우에서 탐색할 수 있도록 방문 체크를 해제해주어야 합니다.

코드

#include <string>
#include <vector>
#include <climits>
#include <iostream>

using namespace std;

static bool visited[8]={};
static int answer=-1;

void DFS(int k, vector<vector<int>>& dungeons, int depth)
{
    
    answer = max(answer, depth);
    for(int i=0; i<dungeons.size(); i++)
    {
        if(!visited[i] && dungeons[i][0] <= k)
        {
           visited[i]=true;
           DFS(k-dungeons[i][1], dungeons, depth+1);     
           visited[i]=false;
        }
    }
    
}

int solution(int k, vector<vector<int>> dungeons) {
    
    DFS(k, dungeons, 0);
    
    
    return answer;
}