[프로그래머스 LV2] - 피로도(트리) c++

문제

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

프로그래머스

접근방법

백트래킹 재귀함수를 이용해서 풀었다.

코드

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

using namespace std;

int back_tracking(int k, vector<vector<int>> dungeons) {
    int answer = 100;
    int n = dungeons.size();
    //던전을 도는 경우의 수 최대 8!
    bool check_leaf = true;
    if (!dungeons.empty() && k) {
        for (int i=0;i < n;i++) {
            if (k >= dungeons[i][0]) {
                vector<vector<int>> temp;
                for (int j=0; j < n;j++) {
                    if (j != i) temp.push_back(dungeons[j]);
                }
                int nk = k - dungeons[i][1];
                answer = min(answer, back_tracking(nk, temp));
                check_leaf = false;
            }
        }
    }
    if (check_leaf) {
        return dungeons.size();
    }
    return answer;
}

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

개선할 점

...