[프로그래머스] 피로도 (C++)

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/87946

코딩테스트 연습 - 피로도

1. 주의할 점

- 최소 피로도 ≥ 소모 피로도

 

2. 구현

- 최소 피로도를 needEnergy[] 배열에 담는다

- 소모 피로도를 useEnergy[] 배열에 담는다

- check[] 배열을 통해 던전 탐험 유무를 체크한다

- DFS()를 수행하며 남은 피로도가 최소 피로도 이상이며, 탐험하지 않은 던전인 경우, 탐험을 한다

#include <string>
#include <vector>
#include <cmath>
using namespace std;
int needEnergy[8];
int useEnergy[8];
bool check[8]={false,};
int num;
int result=0;

void dfs(int cnt, int remain){
    for(int i=0;i<num;i++){
        if(!check[i] && needEnergy[i]<=remain){
            check[i]=true;
            dfs(cnt+1,remain-useEnergy[i]);
            check[i]=false;
        }
    }
    result = max(result,cnt);
    return;
}

int solution(int k, vector<vector<int>> dungeons) {
    int answer = -1;
    num = dungeons.size();
    for(int i=0;i<num;i++){
        needEnergy[i] = dungeons[i][0];
        useEnergy[i] = dungeons[i][1];
    }
    dfs(0,k);
    return answer = result;
}