Level 2. 피로도

Level 2. 피로도

 

 

처음엔 이 문제가 그리디 문제인 줄 알았다.

 

그런데 가장 최소 피로도가 높은 순으로 생각해봐도, 가장 소모 피로도가 낮은 순으로 생각해봐도 맞는 방법이 아니라는 걸 알았다.

 

결국 순열을 만들어 모든 경우의 수를 계산해야 한다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int k, vector<vector<int>> dungeons)
{
    int answer = -1;
    size_t size = dungeons.size();
    vector<int> pmt(size);

    for (int i = 0; i < size; ++i)
        pmt[i] = i;

    do
    {
        int cnt;
        int stamina = k;

        for (cnt = 0; cnt < size && 0 < stamina; ++cnt)
            if (dungeons[pmt[cnt]][0] <= stamina)
                stamina -= dungeons[pmt[cnt]][1];
            else
                break;

        answer = max(answer, cnt);
    }
    while (next_permutation(pmt.begin(), pmt.end()));

    return answer;
}

 

 

재귀를 아주 잘 이용한 풀이이다.

 

던전에 입장할 수 있으면 소모 피로도를 소모하고 현재 던전을 제외시켜 다음 재귀함수에 전달하는 방식이다.

 

solution() 함수는 전달 받은 각 던전을 첫 번째로 방문했을 때의 해답의 최댓값을 구한다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int k, vector<vector<int>> dungeons)
{
    int answer = -1;

    for (auto it = dungeons.begin(); it != dungeons.end(); ++it)
    {
        if ((*it)[0] <= k)
        {
            auto next_dungeons = dungeons;

            next_dungeons.erase(next_dungeons.begin() + (it - dungeons.begin()));

            answer = max(answer, solution(k - (*it)[1], next_dungeons) + 1);
        }
    }

    return answer;
}