프로그래머스 피로도 C++

문제 설명

 

입출력 예

k                           dungeons                                                                                                                                  result

80

[[80,20],[50,40],[30,10]]

3

 

 

=> 처음에는 DFS 혹은 BFS로 풀어야 하는 문제라고 생각했습니다. 

=> 하지만 제한사항을 보면, dungeons의 길이는 최대 8개입니다. 

=> 완전탐색을 해도 되는 조건이므로 완전 탐색을 시행하였습니다. 

=> <algorithm> 헤더에 포함되어있는 next_permutation함수를 이용하였습니다. 

 

https://codingham.tistory.com/262

순열과 조합의 차이

 

 

=> 순열과 조합에 대해 정리해두었습니다. 참고부탁드립니다. 

=> 풀이내용은 아래 사진과 같습니다. 

 

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

using namespace std;

int solution(int k, vector<vector<int>> dungeons) {
    int answer = 0;
    
    vector<int> dungeonsArr; //던전배열_순열에사용
    for(int i=0; i<dungeons.size(); i++)
    {
        dungeonsArr.push_back(i);
    }
    
    do
    {
        int tmpK = k;
        int step = 0;
        for(auto idx : dungeonsArr)
        {
            int needFatig  = dungeons[idx][0]; //최소필요피로도
            int spendFatig = dungeons[idx][1]; //소모피로도
            if(tmpK < needFatig)//현재피로도 < 최소필요피로도
            {
                break;
            }
            else
            {
                tmpK -= spendFatig;
                step++;
            }
        }
        if(step > answer)answer=step;
    }while(next_permutation(dungeonsArr.begin(), dungeonsArr.end()));
    
    return answer;
}