[ 프로그래머스 ] 피로도

문제

---

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

풀이

---

이는 DFS 문제로, 탐험 횟수마다 필요한 피로도가 다른데, 최대 탐험 횟수를 이루는 경우를 찾는 것이다, 이를 찾기 위해 다음 탐험에 필요한 피로도가 현재 피로도보다 낮을 때를 구하고, 이중 가장 많은 탐험 횟수를 저장하여 이를 return한다.

#include <string>
#include <vector>

using namespace std;

int isVisit[9] = { false };
vector<vector<int>> dungeon;
int answer = -1;

void dfs(int k, int cnt) 
{
    if (k < 0) 
    {
        return;
    }

    for (int i = 0; i < dungeon.size(); i++) 
    {
        if (!isVisit[i] && k >= dungeon[i][0]) 
        {
            isVisit[i] = true;
            dfs(k - dungeon[i][1], cnt + 1);
            isVisit[i] = false;
        }
    }

    answer = max(answer, cnt);
}

int solution(int k, vector<vector<int>> dungeons) 
{
    dungeon = dungeons;
    dfs(k, 0);

    return answer;
}