[Programmers] 피로도

• 문제
  

• 코드

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int solution(int k, vector<vector<int>> dungeons) {
    int answer = -1;
    vector<int> permution;
    for(int i=0; i<dungeons.size(); i++){
        permution.push_back(i);
    }
    
    do {
        int now = k;
        int cnt = 0;
        for(int i=0; i<permution.size(); i++){
            if(now>=dungeons[permution[i]][0]){
                now-=dungeons[permution[i]][1];
                cnt++;
            }
            else break;
        }
        if(answer<cnt) answer = cnt;
    } while (next_permutation(permution.begin(), permution.end()));
    
    return answer;
}

• 풀이

DP인가 했는데, 방문 순서에 따라 결과가 달라지는 걸 봤을 때 그냥 분류된대로 완전탐색이구나 했다.
완전 탐색을 좀 찾아보고 풀어봐야겠다 싶어서 블로그 정리 글을 참고했다.
https://hongjw1938.tistory.com/78
순열을 구현하는 방법도 블로그에 정리돼있다.

완전탐색을 하는 방법중 순열이 있는데, 순서에 따라 결과가 달라지는 게 딱 이 문제랑 같아서 순열 알고리즘을 이용하였다.

알고리즘이 좀 복잡해서 완벽히 이해는 못 했는데 cpp는 algorithm라이브러리에서 기능을 제공해줘서 이용하였다.

• 완전탐색의 경우는 경우의 수가 크면 시간복잡도가 너무 커질 수 있어서 문제를 파악하고 사용가능한지 확인하는 게 중요하다.
  이 문제는 던전의 최대 개수가 8로 순열을 이용하면 최대 8! * 8 번 탐색하게 된다.

• 순열 알고리즘을 이용해 인덱스를 배치하고, 해당 순서대로 던전을 방문한다.

• 피로도를 업데이트 해주며, 더 이상 다음 순서를 방문할 수 없으면 반복문을 탈출하고 answer을 업데이트 해준다.