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

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

프로그래머스

 

#include <string>
#include <vector>

using namespace std;

int maxCnt=-1;
vector<bool> ch(8,0);
int enterCnt=0;

void recur(int curk,const vector<vector<int>>& dungeons)
{
    for(int i=0;i<dungeons.size();i++)
    {
        if(ch[i]==false&&curk>=dungeons[i][0])
        {
            enterCnt++;
            ch[i]=true;
            recur(curk-dungeons[i][1],dungeons);
            ch[i]=false;enterCnt--;
        }
    }
    if(enterCnt>maxCnt)
            maxCnt=enterCnt;
}

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

 

피로도를 사용하여 가장 많은 수의 던전을 공략할 때, 몇개까지가능한지를 리턴하는문제이다. 

이런 완전탐색의 문제는 재귀함수로 구현하는 것이 가장 깔끔해서 재귀함수로 구현했다. 

 

현재 던전을 공략했는지를 나타내는 ch 라는 bool 벡터를 생성했다. 

재귀함수에서 ch와 curk를 통해서 이 던전에 입장이 가능한지 판단 후 입장을 진행한다.

이 때, 입장은 재귀함수를 호출하는 것이다. 

 

그리고 그 입장한 수를 enterCnt로 저장하였다. 

그렇게 for문이 종료되었을 때는 현재상황에서 방문하지 않은 각 던전을 방문했을 때의 최댓값이 entercnt에 저장된다.

따라서 dungeons.size() 번의 재귀에서 if문으로 max가 결정될 거고 모든 재귀가 종료되면 max값을 리턴하면 된다.