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

풀이

카테고리가 완전탐색이기도 하지만 던젼길이가 최대 8이기 때문에 완전탐색으로 풀어도 된다고 생각했다.

백트래킹을 이용해서 던전을 방문하는 순서를 모두 탐색한다.

던젼을 선택할때 남은 피로도로 탐색할수있는지 검사한다. 스코어가 0보다 작다면 더이상 탐색못하므로 return해준다.

#include <string>
#include <vector>

using namespace std;
vector<vector<int>> dungeon;
vector<bool>chk;
int answer;
void dfs(int score,int cnt){
      
    //남은 피로도가 없음녀 탐색 끝
    if(score<0)
        return;
    //최대갯수 갱신
    if(cnt>answer)
            answer=cnt;
       
    for(int i=0;i<dungeon.size();i++){
        //던젼을 탐색할 수 있는 남은 피로도 검사
        if(chk[i] || score<dungeon[i][0])
            continue;
        chk[i]=true;
        dfs(score-dungeon[i][1],cnt+1);
        chk[i]=false;
    }
    
}
int solution(int k, vector<vector<int>> dungeons) {
    
    dungeon = dungeons;
    chk.resize(dungeons.size());
    dfs(k,0);
    return answer;
}