프로그래머스 - 피로도

프로그래머스 - 피로도

던전을 탐험할 수 있는 경우의 수를 순열로 뽑는다.

• 던전의 갯수가 1이상 8이하여서 순열로 해도 괜찮을 거라고 판단함.

순열을 구한 뒤 문제에 주어진 조건에 따라서 탐험 가능 여부를 체크하고 탐험 던전 갯수를 체크해서 가장 큰 값을 반환해주면 된다.

#include <string>
#include <vector>
#include <cstdio>
#include <algorithm>

using namespace std;

int order_arr[10];
int visit[10];
int answer = -1;
void combination(int k, int n, int depth, const vector<vector<int>> &d) 
{
    if(n == depth) {
        int local_visit = 0;
        for(int i=0;i<n;i++) {
            if(k < d[order_arr[i]][0])
                break;
            local_visit++;
            k -= d[order_arr[i]][1];
        }
        
        answer = max(answer, local_visit);
        return;
    }
    for(int i=0;i<n;i++) {
        if(visit[i] == 0) {
            visit[i] = 1;
            order_arr[depth] = i;
            combination(k, n, depth + 1, d);
            visit[i] = 0;
        }
    }
}
int solution(int k, vector<vector<int>> dungeons) {    
    combination(k, dungeons.size(), 0, dungeons);
    
    return answer;
}