피로도(16분)

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

구현 아이디어 2분 구현 14분

풀이

// 던전의 개수가 작기 때문에(1 이상 8 이하) 완전 탐색 가능.
// 구현 아이디어 2분. 구현 14분.
#include <string>
#include <vector>

using namespace std;
// 방문 확인, 조합 배열.
int check[8], result[8];
int max_dungeons = -2147000000, K;

void DFS(int L, int num_dungeons, const vector<vector<int>>& dungeons)
{
    // 구한 조합으로 최대 던전 수 계산.
    if(L == num_dungeons)
    {
        int tmp = K, i = 0;
        for(; i < num_dungeons; ++i)
        {
            int idx_dungeon = result[i];            // 방문할 던전.
            int need = dungeons[idx_dungeon][0];    // 최소 필요 피로도.
            int use = dungeons[idx_dungeon][1];     // 소모 피로도.
            
            if(tmp < need) break;
            else if(tmp < use) break;
            else tmp -= use;
        }
        
        if(max_dungeons < i)
            max_dungeons = i;
        
        // 디버깅.
        //for(auto it : result)
            //printf("%d ", it);
        //printf("\n");
    }
    else
    {
        for(int i = 0; i < num_dungeons; ++i)
        {
            if(check[i] == 0)
            {
                check[i] = 1;
                result[L] = i;
                DFS(L + 1, num_dungeons, dungeons);
                check[i] = 0;
            }
        }
    }
}

int solution(int k, vector<vector<int>> dungeons) {
    int answer = -1;
    K = k;
    
    // 던전 개수.
    int num_dungeons = dungeons.size();
    DFS(0, num_dungeons, dungeons);
    
    return answer = max_dungeons;
}