[프로그래머스 고득점kit] 완전탐색_피로도(c++)(순열 풀이)

https://school.programmers.co.kr/learn/courses/30/lessons/87946?language=cpp 

프로그래머스

dfs가 바로 떠올랐다. 하지만 완전탐색으로 분류된 문제인 만큼 완전탐색으로 풀고 싶었다.

순열을 순회할 수 있는 next_permutation함수를 사용하여 해결했다. 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int get_explore_cnt(vector<int> v, vector<vector<int>> dungeons, int k)
{
    int cnt = 0;
    
    for (int i = 0; i < v.size(); i++)
    {
        if (k >= dungeons[v[i]][0])
        {
            cnt++;
            k -= dungeons[v[i]][1];
        }
    }
    return (cnt);
}

int solution(int k, vector<vector<int>> dungeons) {
    int answer = -1, i = 0;
    
    vector<int> v(dungeons.size());
    
    for (int i = 0; i < v.size(); i++)
        v[i] = i; // 오름차순 순열 만들어줌
    while (1)
    {
        answer = max(answer, get_explore_cnt(v, dungeons, k));
        if (!next_permutation(v.begin(), v.end())) // 다음 순열이 있으면 바꿔주고 없으면 break
            break ;
    }
    return answer;
}