[Programmers] 피로도 (Lv.2)

풀이 소요시간 : 30분

정말 오랜만에 코딩테스트 문제를 풀었다. 이번에는 유형이 주어진 문제를 풀었는데, 완전탐색 이라는 키워드를 보고 백트래킹 을 이용한 조합 구하기 문제라는 것을 유추할 수 있었다.

다만 이전에 풀었던 백트래킹 문제들과 다르게 탐색 중단 의 포인트가 조금 달라서 그 부분을 고민하는데 시간을 소요했다. 전체 코드는 다음과 같다.

전체 코드

#include <string>
#include <vector>

using namespace std;

int N, K;
int Visit[8];
int Map[8][2];
int Ans = -999; 

void Dfs(int Count, int K) {
    
    for(int i = 0; i < N; i++)
    {
        if(K < Map[i][0] || Visit[i] == 1) continue;
        
        Visit[i] = 1;

        Dfs(Count + 1, K - Map[i][1]);
        
        Visit[i] = 0;
    }
    //다 살펴봤는데 가능한 경우가 없는 경우
    
    Ans = max(Ans, Count);
    return;
    
}

int solution(int k, vector<vector<int>> dungeons) {
    
    N = dungeons.size();
    K = k;
    
    for(int i = 0; i < N; i++)
    {
        Map[i][0] = dungeons[i][0];
        Map[i][1] = dungeons[i][1];
    }
    //전역변수 세팅
    
    Dfs(0, K);
    //백트래킹
    
    return Ans;
}