[c++] 프로그래머스 - 피로도(Level 2)

문제

코딩테스트 연습 - 피로도

 

코드

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

using namespace std;

int ans = 0;

int backtracking(vector<int> visited, int explore_cnt, int curr_point, vector<vector<int>>& dungeons){
    
    for(int i=0; i<dungeons.size(); i++){
        int need_point = dungeons[i][0];
        int use_point = dungeons[i][1];
        
        if(curr_point>=need_point){
            if(!visited[i]){
                visited[i]=1;
                ans = max(ans, backtracking(visited, explore_cnt+1, curr_point - use_point, dungeons));
                visited[i]=0;
            }
            
        }
    }
    return explore_cnt;
}

int solution(int k, vector<vector<int>> dungeons) {
    vector<int>visited(50);
    backtracking(visited,0,k,dungeons);
    
    return ans;
}

 

풀이

완전 탐색 문제인데 해당 던전을 고르는데 순서가 없기 때문에 방문 처리를 해가면서 모든 경우의 수를 따져야 하는 문제입니다. 문제 자체는 크게 어렵지 않았고 흔한 백트랙킹을 이용하는 흔한 완전 탐색 문제 중 하나였습니다.