프로그래머스 - 피로도

 코딩테스트 고득점 Kit 완전탐색 Level 2 피로도 문제이다. 이 문제는 완전 탐색, 백트래킹을 이용한 기초적인 문제이다. 던전이 최대 8개까지밖에 없기 때문에, k가 충분히 커서 모든 던전을 다 돌수 있다고 가정해도 8! = 40320번 밖에 되지 않는다. 

 

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

using namespace std;

int result;
vector<bool> visited;

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

int solution(int k, vector<vector<int>> dungeons) {
    int answer = -1;
    
    visited = vector<bool>(dungeons.size(), false);
    
    func(dungeons, k, 0);
    
    answer = result;
    
    return answer;
}