[프로그래머스] 피로도

풀이 : 

처음 접근했을 떄, 생각난 방법은 필요 피로도는 내림차순 소모 피로도는 오름차순으로 정렬 후 

그리디로 접근하는 방법을 생각했다. 하지만 조건을 확인해보니, 던전이 8개로 제한 되있다.

때문에 안전하게 모든 경우의 수를 모두 탐색하는 방법으로 선택하였다.

 

 

방법 1) 

 

- next_permutation 

모든 경우의 순열을 만들도록 사용했다 

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

void permutation(int k, vector<vector<int>>& dungeons, int & answer){
    vector<int> per;
    int tempK = k;
    for(int i=0;i<dungeons.size();i++){
        per.push_back(i);
    }
    do{
        tempK = k;
        for(int i=0; i<per.size();i++){
            int next = per[i];
            int minValue = dungeons[next][0];
            int consumeValue = dungeons[next][1];
            
            if(tempK>=minValue){
                tempK-= consumeValue;
                answer = max(answer,i+1);
                
            }else break;
            
        }
        
    }while(next_permutation(per.begin(), per.end()));
    
 
   
}

int solution(int k, vector<vector<int>> dungeons) {
    int answer =-1;
    permutation(k, dungeons, answer);
    return answer;
    
    
    
}

 

방법 3) DFS로 접근하는 방법

#include <string>
#include <vector>
#include <queue>
int answer = 0;
bool check[9]= {false,};
using namespace std;
void DFS(int now, int k, vector<vector<int>> dungeons){
    if(answer < now) answer= now;
    for(int i=0;i < dungeons.size();i++){
        if(check[i] || dungeons[i][0] > k) continue;
        check[i] =true;
        DFS(now+1, k-dungeons[i][1], dungeons);
        check[i]= false;
        
    }
    
}

int solution(int k, vector<vector<int>> dungeons) {
    
    DFS(0,k, dungeons);
    return answer;
}