[프로그래머스 위클리 챌린지] 피로도 (완전탐색, next_permutation) [C++]

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

코딩테스트 연습 - 피로도

 

각 던전에는 입장할 수 있는 최소 피로도, 던전을 돌고 나면 소모되는 피로도가 주어진다.

전체 피로도가 주어지고, 던전을 입장하면서 최대 몇 개의 던전을 돌 수 있는지 구한다.

 

처음엔 그리디 같은 걸 생각했지만, 던전의 개수도 8개 이하이기 때문에 완전 탐색으로 풀었다.

완전 탐색으로 던전을 진입하는 순서를 만들고, 각 순서 쌍마다 다 던전을 돌아보는 방법이다.

 

즉, 던전이 4개라면 던전을 입장하는 순서를 순열로 만든다면

1 2 3 4, 1 2 4 3, .... 4 3 2 1 등이 있을 것이고 이걸 next_permutation으로 만들었다.

 

- 던전을 입장할 수 있는 모든 순서쌍을 만들고 피로도를 계산해보는 완전 탐색 풀이 방법

- next_permutation으로 순서쌍을 만들기 위해서 0 1 2 3을 벡터에 넣어주고 돌렸다.

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

using namespace std;

void permutation(int k, vector<vector<int>> & dungeons, int & answer){
    vector<int> per;
    int tempK = k;
    for(int i = 0 ; i < dungeons.size() ; i++){
        per.push_back(i);
    }
    do{
        tempK = k;
        for(int i = 0 ; i < per.size() ; i++){
            int next = per[i];
            int minValue = dungeons[next][0];
            int consumeValue = dungeons[next][1];
            
            if(tempK >= minValue){
                tempK -= consumeValue;
                answer = max(answer, i+1);
            }
            else{
                break;
            }
        }
    } while(next_permutation(per.begin(), per.end()));
}

int solution(int k, vector<vector<int>> dungeons) {
    int answer = -1;
    permutation(k, dungeons, answer);
    return answer;
}