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

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

코딩테스트 연습 - 피로도

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int k, vector<vector<int>> dungeons) {
    int answer = -1;
    vector<int> perm;
    for (int i=0; i<dungeons.size(); i++)
        perm.push_back(i);
    do{
        int tired=k;
        bool flag=false;
        for (int i=1; i<=dungeons.size(); i++){
            int order=perm[i-1];
            if (tired<dungeons[order][0]){
                answer=max(answer, i-1);
                flag=true;
                break;
            }
            tired-=dungeons[order][1];
        }
        if (!flag){
            answer=dungeons.size();     //모든 던전 탐험 가능한 경우
            break;
        }
    } while (next_permutation(perm.begin(), perm.end()));
    return answer;
}

 

순열로 모든 case를 검사하는 형태이다.

 

피로도가 기준에 충족되지 않으면 그때 비교해서 answer 값을 구한다.

 

그러나 dfs 이용해 모든 경우를 탐색할 수 있다. (참고: https://katfun.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%94%BC%EB%A1%9C%EB%8F%84)

 

시작점을 고정하고, dfs 로 탐색하면서 탐색가능한 최대값의 던전을 갱신해주는 식이다.