[프로그래머스 lv2] 피로도 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

 

던전을 탐험하는 순서에 따라 최대로 이동할 수 있는 던전의 수가 달라진다.

던전을 탐험하는 모든 경우의 수에 대하여 이동할 수 있는 던전 수를 확인하고 이들 중 최댓값을 리턴하면 정답이다.

 

재귀를 이용해 모든 경우의 수를 확인할 수도 있지만, next_permutation() 함수를 활용하면 모든 던전 순서쌍을 간단히 확인할 수 있다.

각 던전 순서쌍에 대하여 남아있는 피로도가 최소 피로도보다 크거나 같을 때까지 cnt를 증가시키고, 계산된 cnt 값 중 최댓값을 리턴한다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

int solution(int k, vector<vector<int>> dungeons) {

    vector<int> v(dungeons.size());
    for (int i=0; i<v.size(); i++)
        v[i] = i;

    int mx = 0;
    do {
        int cnt = 0;
        int score = k;
        for (int i=0; i<v.size(); i++) {
            if (score < dungeons[v[i]][0]) break;
            cnt++;
            score -= dungeons[v[i]][1];
        }
        mx = max(mx, cnt);
    } while (next_permutation(v.begin(), v.end()));

    return mx;
}