피로도 / 브루트 포스 기법(순열)

처음에 이 문제를 접했을 때, priority_queue를 사용해 던전의 최소 피로도가 큰 기준, 최소 피로도가 같다면 소모 피로도가 작은 기준이 우선 순위가 높도록하여 던전 입장 횟수를 카운팅 해주면 될 것으로 판단했다.

 

✅ priority_queue를 사용한 코드

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(int k, vector<vector<int>> dungeons)
{
    struct compare
    {
        bool operator()(const pair<int, int>& a, const pair<int, int>& b)
        {
            if (a.first == b.first) return a.second > b.second;
            return a.first < b.first;
        }
    };

    priority_queue<pair<int, int>, vector<pair<int, int>>, compare> pq;

    for (int i = 0; i < dungeons.size(); ++i)
    {
        pq.push({dungeons[i][0],dungeons[i][1]});
    }

    int answer = 0;
    while (!pq.empty())
    {
        pair<int, int> p = pq.top();
        pq.pop();

        if (k < p.first) continue;
        if (k <= 0) break;

        k -= p.second;
        answer++;
    }

    return answer;
}

int main()
{
    int k = 80;
    vector<vector<int>> dungeons = { {80, 20},{50,40},{30, 10} };

    int result = solution(k, dungeons);


    return 0;
}
// 1. 던전 피로도 priority_queue에 최소 필요도가 큰 기준, 소모 피로도 작은 기준으로 정렬
// 2. 현재 피로도 k가 소모될 때까지 카운팅

🚫오류 상황

입출력 예시를 보면 기대값이 3인데, 2의 결과 값이 나왔다.
현재 우선순위 큐를 사용했을 때 예시 그대로 {80, 20}, {50, 40}, {30, 10} 순서로 한 번 던전 입장 횟수를 카운팅한다. 하지만 {80, 20}, {30, 10}, {50, 40} 순서로 던전에 입장해야 3번 입장할 수 있게되고 최대 값을 구하게된다.

뒤늦게 문제를 꼼꼼히 보았더니 던전의 최대 개수를 보니 8개로 작은 값인 것을 확인했고, 모든 순서로 던전 입장 횟수를 카운팅해 최대 입장 가능 횟수를 구해야 함을 직감했다.

어제 챌린지반에서 공부했던, 모든 경우의 수를 전부 탐색하는 브루트 포스 기법이 떠올랐고, 그 중 순열을 사용한 완전탐색으로 문제를 해결하려 했다.

 

✅ 브루트 포스(순열) 기법으로 문제 해결

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

using namespace std;

int solution(int k, vector<vector<int>> dungeons)
{
    // 브루트 포스 기법, 순열을 사용해서 모든 경우를 카운팅해보기
    
    sort(dungeons.begin(), dungeons.end());

    int max_cnt = -1;
    int origin_k = k;

    do
    {
        int cnt = 0;
        int k = origin_k;

        for (const auto& row : dungeons)
        {
            if (k < row[0]) continue;

            k -= row[1];
            cnt++;
        }

        if (cnt > max_cnt) max_cnt = cnt;
    } while (next_permutation(dungeons.begin(), dungeons.end()));

    return max_cnt;
}

algorithm 의 next_permutation 을 사용해서 모둔 경우의 수를 탐색하는 방식으로 문제를 해결했고 기댓값에 맞는 결과값을 얻을 수 있었다.
next_permutation을 사용하기 전에 반드시 사전 순으로 정렬이 되어있어야 했는데, 이를 깜빡해서 정렬을 안하고 실행하니 do-while문 루프가 한 번만 실행되어 결과 값이 계속 2가 나오는 오류가 있었다..; 정렬을 반드시 하자!