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

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

프로그래머스

---

풀이

던전의 개수가 최대 8개이므로 모든 경우의 수를 확인하며 가장 많은 던전을 도는 경우를 찾았다.

이 때 DFS로 탐색하며 현재 탐색한 던전의 개수를 저장하고, 최댓값과 비교하며 갱신한다.

---

코드

#include <string>
#include <vector>

using namespace std;

bool visited[10];
int maxCnt = -1;

void dfs(vector<vector<int>>& dungeon, int k, int cnt) {
    
    for (int i = 0; i < dungeon.size(); i++) {
        auto d = dungeon[i];
        
        // 이미 방문함 || 현재 피로도 < 최소 필요 피로도
        if (visited[i] || k < d[0]) continue;
        
        visited[i] = true;
        dfs(dungeon, k - d[1], cnt + 1);
        visited[i] = false;
    }
    maxCnt = max(maxCnt, cnt);
}

int solution(int k, vector<vector<int>> dungeons) {
    dfs(dungeons, k, 0);
    return maxCnt;
}