프로그래머스 피로도 c++

#include <string>
#include <vector>
#include <cmath>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int answer = -1;
bool check[9];

int solution(int k, vector<vector<int>> dungeons) {
    vector<int> v;
    for(int i=0; i<dungeons.size(); i++) {
        v.push_back(i);
    }
    
    do {
        int tmp = k;
        int cnt = 0;
        for(int i=0; i<v.size(); i++) {
            if(tmp >= dungeons[v[i]][0]) {
                tmp -= dungeons[v[i]][1];
                cnt++;
            }
            else {
                break;
            }
        }
        answer = max(answer, cnt);
    } while (next_permutation(v.begin(), v.end()));
    
    
    return answer;
}

** 완전탐색 문제

최대 8개

factorial(8) 은 1억 이하기 때문에 시간복잡도에 걸릴일이 없다.

 

전체 경우의 수를 순회하며 가장 큰 경우를 반환해주면 된다.