[C++] 피로도

처음에는 던전을 정렬하려고 했다.
던전당 최소 피로도 내림차순 -> 예제에서 털림
던전당 소모 피로도 오름차순(소모 피로도가 같다면 최소 피로도 내림차순) -> 예제에서 털림
모든 변수를 고려한 정렬의 방법이 있었을지 모르겠지만, 일단 나는 정렬로 풀기는 실패했다.
결국 모든 경우의 수 고려하기가 채택되었다.

이게 깊이우선탐색을 사용하면 될거란 생각은 들었는데, 아직 제대로 그쪽 공부를 안해서 되는대로 풀었다.
나는 next_permutation을 활용했음
다만 삽질을 좀 한게, 던전 당 최소 피로도가 같다면, 던전당 소요 피로도가 가장 작은얘 하나만 남겨둬도 된다고 생각했다는 점^^;; 그거때문에 케이스4에서 계속 오류가 났음.
이에 대한 반례는 감사하게도 질문하기에서 찾을 수 있었음!
40, [[40, 20], [10, 10], [10, 10], [10, 10], [10, 10]], 4 여기서 내 맘대로 [40,20][10,10] 으로 던전을 압축시켜버렸기 때문임

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

using namespace std;

int solution(int k, vector<vector<int>> dungeons) {
    int dungeons_size = dungeons.size();
    int answer = 0;    
    sort(dungeons.begin(),dungeons.end());
    
    do {
        int count = 0;
        int currentK = k;
        for(auto ele : dungeons) {
            if(currentK >= ele[0]) {
                currentK-=ele[1];
                count++;
            } else if(currentK == 0) {
                break;
            }
        }
        
        if(count == dungeons_size) {
            answer = count;
            break;
        } else if(count > answer) {
            answer = count;
        }
        
    }while(next_permutation(dungeons.begin(),dungeons.end()));
    return answer;
}

주어진 던전 벡터를 오름차순 정렬한 뒤, next_permutation을 do_while로 돌려서 최대카운트를 반환하게끔 한다.
여기서 연산을 좀 빠르게 할 수 있도록, 던전탐색 중 피로도가 0이면 break하게 하기, 카운트 값이 이미 던전이 개수와 같으면 do_while문을 break하게 했다.

아 요즘 나와서 아이패드로 프로그래머스를 돌리는데, 아이패드는 ctrl+space를 눌러야 한영 전환이 됨.
주석 붙이고 싶은데 이게 귀찮아서 안붙여버릇하네... ㅋㅋㅋ

이번에 깨달은 것은, 효율적인 방식을 고려하는 것도 좋으나 내 선에서 그게 안될 것 같으면 무식해보여도 완전탐색을 과감히 빠르게, 적용시켜봐야 한다는 점이었음
시간 제한이 있는 테스트에서 방향 빠르게 찾기는 중요하다.