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

 

https://programmers.co.kr/learn/courses/30/lessons/87946

코딩테스트 연습 - 피로도

 

글쓴이의 답

개인적인 풀이 임으로

이것보다 더 좋은 알고리즘은 많음...

이렇게도 풀이하는구나.. 공유하기 위해 올림...

 

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int dfs(int k, vector<bool> &check, vector<vector<int>> &dungeons, int location, int &result, int count){
    
    if( (0 > k - dungeons[location][0]) ){ 
        if(count > result){
            result = count;
        }
        return 0;
    }
    
    count++;
    if(count ==check.size()){
        result = count;        
        return 0;
    }
    
    k = k - dungeons[location][1];
    
    
    
    for(int i=0; i<dungeons.size(); i++){
        if(true == check[i]){
            continue;
        }
        check[i] = true;        
        dfs(k, check, dungeons, i, result, count);
        check[i] = false;        
    }
    return 0;
}

int solution(int k, vector<vector<int>> dungeons) {
    int answer = -1;
    
    int mapSize = dungeons.size();
    vector<bool> check(mapSize);
    
    int count = 0;
    
    for(int i=0; i<dungeons.size(); i++){
        if(true == check[i]){
            continue;
        }
        check[i] = true;
        dfs(k, check, dungeons, i, answer, count);
        check[i] = false;        
    }
    
    return answer;
}

꾸준히 하다보면 실력이 늘겠지..