프로그래머스 피로도

문제

쉽게 정리하면 던전들의 정보가 주어지는데 던전을 돌 수 있는 조건인 최소 피로도와 던전을 돌면 감소하는 피로도가 주어진다

그래서 던전들의 순서를 다르게 해서 최대로 던전을 돌 수 있는 경우의 수를 찾는 문제

풀이

문제에서 핵심을 찾아보면 우선 입력으로 주어지는 던전의 개수가 매우 작다

그리고 던전의 순서를 다르게 한다는 것에서 나는 이 문제를 순열로 풀 수 있다고 생각했다

C++에는 순열을 쉽게 구할 수 있는 함수인 next_permutation(시작, 끝)이 있기에 이 함수를 사용했다

이 함수를 사용하려면 먼저 리스트를 오름차순으로 정렬하고 do-while 문을 통해 가장 먼저 정렬된 배열로 탐색하고 반복문이 끝나면 함수를 통해 리스트를 순열에 맞게 섞는다

그리고 던전을 돌 수 있는 로직을 맞게 작성해주면 끝

풀이

#include <bits/stdc++.h>

using namespace std;

int solution(int k, vector<vector<int>> dungeons) {
    int answer = -1;
    
    sort(dungeons.begin(), dungeons.end());
    
    do
    {
        int temp = k;
        int count = 0;
        
        for(int i = 0; i < dungeons.size(); i++)
        {
            if(temp >= dungeons[i][0])
            {
                temp -= dungeons[i][1];
                count++;
            }
        }
        
        answer = max(answer, count);
    
    }while(next_permutation(dungeons.begin(), dungeons.end()));
    
    return answer;
}