프로그래머스 - 피로도 (C++)

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

프로그래머스

 

순서를 1 2 3, 2 1 3, 3 1 2 등 어떤식으로 진행해야할지 정하는 문제. 그리디하게 생각할 수 없고 모든 것을 해보는 것이 정답인 경우이다. 겨우 N이 8까지 밖에 없는 경우라서 가능하지만 숫자가 더 커지면 다른 방법을 찾아야한다. 

 

이 문제는 dfs로 순열을 만드는 문제와 유사하다. dfs로 순열 조합을 다룰 줄 알아야한다.

 

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

using namespace std;

int N;
bool check[10] = {false,};

vector<int> vec;
int answer = -1;

void dfs(int k, int n, vector<vector<int>> d){
    if(n == N){
        int cnt = 0;
        for(auto a : vec){
            if(d[a][0] <= k){ // 피로도 가능
                if(d[a][1] <= k){
                    k -= d[a][1];
                    cnt++;
                }
            }
        }
        
        answer = max(answer, cnt);
        
        return;
    }
    
    
    for(int i = 0; i < N; i++){
        if(check[i] == true) continue;
        check[i] = true;
        vec.push_back(i);
        dfs(k, n + 1, d);
        vec.pop_back();
        check[i] = false;
    }
}

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