[프로그래머스/c++] Lv2 피로도

https://school.programmers.co.kr/learn/courses/30/lessons/87946

프로그래머스

완전탐색으로 풀었다.

 

1. exploreDungeon 함수는 주어진 던전을 차례대로 탐험한다. 

2. 주어진 k보다 던전 최소 필요 피로도가 더 작으면 탐험할 수 있기 때문에 던전 소모 피로도를 빼준다. 

3. 만약 최소 필요 피로도가 k보다 크면 break하고 count를 return 해준다. 

4. next_permutation을 사용하기 위해서는 sort 해줘야한다. 

5. answer에 exploreDungeon 함수값과 answer값을 비교한 후 더 큰 값을 넣어준다. 

6. 완전탐색이기 때문에 순열을 사용해준다. 해당 dungeon의 모든 값 (순열)을 구한 후 이 값을 exploreDungeon함수에 넣어주며 최댓값을 찾는다. 

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

using namespace std;

int exploreDungeon(int k, vector<vector<int>>& dungeons) {
    int count = 0;
    for (auto& dungeon : dungeons) {
        int required = dungeon[0];
        int consume = dungeon[1];

        if (k >= required) {
            k -= consume;
            count++;
        }
        else
            break;
    }
    return count;
}
int solution(int k, vector<vector<int>> dungeons) {
    int answer = 0;

    sort(dungeons.begin(), dungeons.end());
    do {
        answer = max(answer, exploreDungeon(k, dungeons));
    } while (next_permutation(dungeons.begin(), dungeons.end()));

    return answer;
}