프로그래머스 - 피로도

프로그래머스 피로도 문제

갖고있는 피로도를 가지고
[입장 피로도, 소모 피로도]를 갖고 있는 던전을
최대 몇개나 돌 수 있는지 구하는 문제이다.

풀이 과정

던전의 갯수가 몇 개 되지 않기 때문에 그냥 DFS로 완전 탐색을 하면 쉽게 풀 수 있을 듯 하여 그렇게 방향을 잡았다.

그리하여 dfs의 방식을 사용하여 완전탐색을 계획하였다.

dfs 구현 방식은 간단히 재귀 방식으로 진행하였다.

dfs에서 조건문을 걸어 백트래킹 느낌으로 구현해보았다.

#include <string>
#include <vector>

using namespace std;

//cur : 현재 피로도 cnt : 현재 입장한 던전 수
void permutation(const vector<vector<int>>& dungeons, vector<int> selected, int cur, int cnt, int& outAnswer)
{   
    cnt++;
    if(cnt>outAnswer)
    {
        outAnswer = cnt;
    }
    for(int i=0;i<dungeons.size();i++)
    {
    	//아직 입장하지 않았고, 현재 피로도로 입장 가능하다면
        if(selected[i] == 0 && dungeon[0]<=cur)
        {
            selected[i] = 1;
            cur -= dungeons[i][1];
            permutation(dungeons, selected, cur, cnt, outAnswer);
            selected[i] = 0;
            cur += dungeons[i][1];
        }
    }
}

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