프로그래머스 레벨2 <피로도> C++ 풀이

완전탐색 혹은 백트래킹 문제를 많이 풀어봤다면 쉬운 문제였다고 생각합니다. 

 

현재 피로도가 입장할 던전의 최소 피로도보다 크거나 같다면 방문처리 및 피로도 감소 처리를 하면서 다시 Search를 호출하는 형태로 진행했습니다. 더이상 들어갈 던전이 없으면 지금까지 들어온 던전의 갯수를 ans에 넣어주고 마지막에 ans를 sort를 이용해 정렬해주면 됩니다. 입력 역시 시간초과에 걸릴만한 크기가 아니기 때문에 비교적 쉽게 정답처리를 받았습니다.

 

 

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int visited[8];
vector<int> ans;
 
void Search(int k,int size,int cnt,vector<vector<int>>& dungeons)
{
    for (int i=0;i<size;i++)
    {
        if (visited[i] == 0 && dungeons[i][0] <= k)
        {
            visited[i] = 1;
            Search(k-dungeons[i][1],size,cnt+1,dungeons);
            visited[i] = 0;
                
        }
    }
    ans.push_back(cnt);    
}
 
int solution(int k, vector<vector<int>> dungeons) {
        
    for (int i=0;i<dungeons.size();i++)
    {
        if (dungeons[i][0] <= k)
        {
            visited[i] = 1;
            Search(k-dungeons[i][1],dungeons.size(),1,dungeons);
            visited[i] = 0;
        }
        
    }
    sort(ans.begin(),ans.end());
    
    return ans.back();
}