[프로그래머스 / C++] 피로도

문제

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

프로그래머스

---

문제 해설

해당 문제는 일정 피로도로 최대한 많은 던전을 들어가는 방법을 찾는 문제이다. 문제의 중요한 조건을 정리하면 아래와 같다.

 

1. 던전에 들어가기 위해서는 최소 필요 피로도 이상의 피로도가 있어야 한다.

2. 던전에 들어가면 소모 피로도만큼 현재 피로도에서 감소한다.

3. 한 번 들어간 던전은 다시 들어갈 수 없다.

4. 던전의 수는 최소 1개, 최대 8개이다.

 

위 조건을 확인하면 DFS를 통한 완전 탐색을 통해 최대 입장 횟수를 구할 수 있다.

 

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<bool> visited;
vector<int> minEnergy;
vector<int> useEnergy;

int maxEnter = 0;
int dungeonSize = 0;

void enterTheDungeon (int count, int energy){
    for(int i = 0; i < dungeonSize; i++){
        if(!visited[i] && energy >= minEnergy[i]){
            visited[i] = true;
            enterTheDungeon(count+1,energy-useEnergy[i]);
            visited[i] = false;
        }
    }
    if(maxEnter < count){
        maxEnter = count;
    }
}


int solution(int k, vector<vector<int>> dungeons) {
    int answer = -1;
    dungeonSize = dungeons.size();
    
    for(vector<int> x : dungeons){
        visited.push_back(false);
        minEnergy.push_back(x[0]);
        useEnergy.push_back(x[1]);
    }
    
    enterTheDungeon(0,k);
    return maxEnter;
}