[Algorithm] Programmers :: 피로도

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

프로그래머스

int result = 0;
vector<int> checkMap(8, 0);
 
void DFS(int k, int index, vector<vector<int>>& dungeons, int count)
{
    int curMin = dungeons[index][0];
    int curCon = dungeons[index][1];
 
    if (k < curMin) // 던전 최소에 못미치면. 
    {
        if (count >= result) result = count;
        return;
    }
 
    k -= curCon;
    checkMap[index] = 1; // index번째 던전 탐사완료.
    count += 1;
 
    for (int i = 0; i < dungeons.size(); i++)
    {
        if (checkMap[i]) continue;
        DFS(k, i, dungeons, count);
        checkMap[i] = 0;
    }
 
    if (count >= result) result = count;
}
 
int solution(int k, vector<vector<int>> dungeons) {
    int answer = -1;
 
    for (int i = 0; i < dungeons.size(); i++)
    {
        DFS(k,i,dungeons, 0);
        checkMap[i] = 0;
    }
 
    answer = result;
 
    return answer;
}

모든 경우의 수를 찾는 완전탐색문제이다.

방문체크를 전역변수로 설정해서 짜려할 경우, DFS돌린 후에 다시 false로 하는걸 잊지말자.

헷갈리면 매개변수에 복사값형태로 방문체크용 컨테이너를 넣어도 되지만, 복사비용이 만만치않고 실제로 이번 문제같은경우도 처음엔 매개변수에 방문체크용map을 복사형태로 넘겼었다.

문제의 경우 던전개수가 최대 8개라 괜찮겠지..라고 생각했고, 실제로 문제없이 통과는 됐다.

다만 대부분케이스들은 0.01~0.03ms선에서 통과됐지만, 몇몇 테스트케이스같은경우는 전역으로 설정했을때와 달리 실행속도가 12~24.ms가 나왔었다. 이것때문에 너무 찝찝해서 방문체크를 전역으로 돌렸더니 전부 다 빠른 실행속도로 통과했다.