[프로그래머스] 피로도

 

 

8! = 완탐으로 풀어도 시간초과 안걸린다.

 

next_permutation을 활용해봤는데 어째 더 긴 것 같다?

#include <string>
#include <vector>
#include <algorithm>
#define MAX(a, b) ((a >= b) ? a : b)
#include <iostream>
using namespace std;

int max_dungeons = 0;

void calculate(int k, vector<int>& permutation, vector<vector<int>>& dungeons) {
    
    int counter = 0;
    
    for(int i = 0; i < permutation.size(); i++) {
        
        if(k >= dungeons[permutation[i]][0]) {
            k -= dungeons[permutation[i]][1];
            counter++;
        } else {
            break;
        }
        
    }
    max_dungeons = MAX(max_dungeons, counter);
    
}

int solution(int k, vector<vector<int>> dungeons) {
    
    int size = dungeons.size();
    
    vector<int> permutation;
    for(int i = 0; i < size; i++) {
        permutation.push_back(i); // e.g) 0 1 2 3 4
    }
    
    do {
        calculate(k, permutation, dungeons);
    } while(next_permutation(permutation.begin(), permutation.end()));
    
    return max_dungeons;
}

 

 

다시 풀었다.

#include <string>
#include <vector>
#define MAX(a, b) ((a>=b) ? a : b)
using namespace std;

int maxAnswer = 0;
bool visit[9];

void dfs(int k, vector<vector<int>>& dungeons, int n, int count) {
    
    maxAnswer = MAX(maxAnswer, count);
    
    for(int i = 0; i < n; i++) {
        
        if(!visit[i]) {
            visit[i] = true;
            if(k >= dungeons[i][0]) dfs(k - dungeons[i][1], dungeons, n, count + 1);
            visit[i] = false;
        }
    }
}

int solution(int k, vector<vector<int>> dungeons) {
    
    dfs(k, dungeons, dungeons.size(), 0);
    
    return maxAnswer;
}