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

프로그래머스

피로도 K와 던전의 [최소 필요 피로도, 소모 피로도]가 담긴 배열을 입력 받을 때, 피로도 K로 돌 수 있는 가장 많은 던전의 수를 구해주세요.

ex) K = 8, dungeons = [[80, 30], [50, 40], [30, 10]] 을 입력 받을 때,

1번 -> 2번 던전을 돌면 3번 던전에 입장하지 못하지만 1번->3번->2번 순서로 돌면 3개의 던전 모두 돌 수 있습니다.

 

풀이 방법

깊이 우선 탐색을 이용하여 모든 경우의 수를 탐색하는 방법을 사용합니다. 

모든 던전에 입장할 수 없을 때 까지 탐색을 진행하고 탐색이 종료되는 시점에 가장 많이 입장한 횟수를 출력합니다

int DFS(int k, vector<vector<int>>& d, vector<bool>& visited, int cnt)
{
    int ret = 0;

    for (int i = 0; i < d.size(); i++)
    {
        if (visited[i] || k < d[i][0])
            continue;
        
        visited[i] = true;
        ret = max(ret, DFS(k - d[i][1], d, visited, cnt + 1) + 1);
        visited[i] = false;
    }
    
    return ret;
}

int solution(int k, vector<vector<int>> dungeons) {
    vector<bool> visited(dungeons.size());
    return DFS(k, dungeons, visited, 0);
}