프로그래머스 문제 - 피로도

프로그래머스 피로도 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

["최소 필요 피로도", "소모 피로도"]식으로 담긴 최대 5000개의 던전이 주어집니다.
k만큼의 피로도가 주어지며 한 던전에 들어가기 위해서는 "최소 피로도" 이상만큼 k를 가지고 있어야 하며 "소모 피로도" 만큼 피로도를 소모하여 던전을 탐험할 수 있습니다.
이때 유저가 탐험할 수 있는 최대 탐험 수를 구해야 합니다.

문제 풀이

던전을 탐험하는 순서에 따라 최대로 탐험할 수 있는 던전의 수가 달라질 수 있습니다.
최대 5000개의 던전이 주어지므로 재귀를 통해 하나씩 모든 던전을 탐험하여 결과를 도출해 낼 수 있습니다.
이때, 한번 탐색한 던전은 다시 탐험할 수 없으며, 탐험한 횟수가 주어진 던전 크기와 같을 경우 그 결과값이 정답이 되므로 함수를 종료하고 답을 내면 됩니다.

전체 코드

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

int answer;
int dungeonSize;

void solve(vector<vector<int>> &dungeons, vector<int> &checkMap, int remainStamina, int exploreCount){
    //탐험한 횟수가 던전 크기와 같을 경우 함수 종료
    if(exploreCount >= dungeonSize)
    {
        answer = exploreCount;
        return;
    }
    
    for(int i = 0; i < dungeonSize; i++)
    {
        //탐험할 수 있는 모든 던전 체크, 이미 들렸던 곳은 다시 가지 못함
        if(dungeons[i][0] <= remainStamina && checkMap[i] == 0)
        {
            checkMap[i] = 1;
            solve(dungeons, checkMap, remainStamina-dungeons[i][1], exploreCount+1);
            checkMap[i] = 0;
        }
        
        if(answer >= dungeonSize)
            return;
    }
    //탐험한 횟수가 이번 탐험 최대 횟수보다 클 경우 최대값 갱신
    if(answer < exploreCount)
    {
        answer = exploreCount;
    }
}

int solution(int k, vector<vector<int>> dungeons) {
    answer = -1;
    vector<int> vec(dungeons.size(), 0);
    dungeonSize = dungeons.size();
    
    for(int i = 0; i < dungeonSize; i++)
    {
        if(dungeons[i][0] <= k && vec[i] == 0)
        {
            vec[i] = 1;
            solve(dungeons, vec, k-dungeons[i][1], 1);
            vec[i] = 0;
        }
        
        if(answer >= dungeonSize)
            return answer;
    }
    
    return answer;
}

출저

https://school.programmers.co.kr/learn/courses/30/lessons/87946?language=cpp#