프로그래머스 - 피로도 C++

April 18, 2023

문제

접근 방식

최대로 돌수 있는 던전 수를 구하기 위해서는 순서대로 모든 경우의 던전들을 둘러보아야 합니다.

DFS로 완전 탐색할 수 있습니다.

풀이

#include <bits/stdc++.h>
#define MAX 8

using namespace std;

int answer = 0;
bool visited[MAX] = {false};

void dfs(int cnt, int k, vector<vector<int>> &dungeons) {
    answer = max(answer, cnt);

    for (int i = 0; i < dungeons.size(); ++i) {
        if (visited[i] || dungeons[i][0] > k) continue;

        visited[i] = true; // 한 depth 아래로 탐색 시작
        dfs(cnt + 1, k - dungeons[i][1], dungeons);
        visited[i] = false; // 탐색 끝났으니 다른 번째에서 다시 탐색할 수 있도록
    }
}

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