[프로그래머스] 피로도

---

🔗 문제 링크

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

프로그래머스

---

728x90

👩‍💻 코드

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

using namespace std;

int solution(int k, vector<vector<int>> dungeons) {
    int answer = 0;
    
    sort(dungeons.begin(), dungeons.end());

    while (next_permutation(dungeons.begin(), dungeons.end())){
        int currentK = k;
        int count = 0;
        
        for (auto dungeon : dungeons) {
            if (currentK >= dungeon[0]) {
                currentK -= dungeon[1];
                count++;
            } else {
                break;
            }
        }

        answer = max(answer, count);
    }
        
    return answer;
}

---

📝 풀이

이 문제는 완전 탐색 알고리즘을 사용해야 한다.

완전 탐색이란 가능한 모든 경우의 수를 일일이 나열하여 답을 찾는 방법이다.

우선 주어진 범위를 순열로 변환해주는 next_permutation을 사용하기 위해 정렬해준다.

각 순열마다 탐험 가능한 수를 카운팅 해준 후 최댓값을 비교하여 갱신한다.

마지막 순열까지 완료하면 갱신된 최댓값을 return 한다.