[Programmers] Level2 : 피로도

Question

---

Solution

• dfs + 백 트래킹으로 모든 경우의 수에 대하여 탐색한다.
• 끝까지 탐색하여 나온 weight를 저장하고 모든 탐색이 끝나면 가장 큰 weight를 구한다.

---

Cord

#include <vector>
#include <string>
#include <algorithm>

using namespace std;

bool visited[8];
vector<int> weight;

// dfs + 백트랙킹
void dfs(vector<vector<int>>& dungeons, int& k, int cnt)
{   
    for(int i = 0; i < dungeons.size(); i++)
    {
        if (!visited[i] && k >= dungeons[i][0])
        {
            visited[i] = true;
            k -= dungeons[i][1];
            dfs(dungeons, k, cnt+1);
            k += dungeons[i][1];
            visited[i] = false;
        }
    }
    
    // 끝까지 탐색하며 나온 weight 저장
    weight.push_back(cnt);
}

int solution(int k, vector<vector<int>> dungeons) 
{  
    dfs(dungeons, k, 0);
    int answer = *max_element(weight.begin(), weight.end());    // 최대값 출력
    return answer;
}

---

Result