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

1. 개요

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

프로그래머스

1-1. 설명

한 게임에 피로도 시스템이 있으며, 일정 피로도를 사용해 던전을 탐험할 수 있다. 각 던전마다 탐험을 시작하기 위해 필요한 최소 필요 피로도와 던전 탐험을 마쳤을 때 소모되는 소모 피로도가 존재한다. 최소 필요 피로도가 80, 소모 피로도가 20인 던전을 탐험하기 위해서 현재 남은 피로도는 80 이상이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모된다. 이 게임은 하루에 한번씩 탐험할 수 있는 던전이 여러개 존재하는데, 한 유저가 최대한 많이 탐험하려고 한다. 한 유저가 탐험할 수 있는 최대 던전 수를 반환하는 함수를 짠다. 

1-2. 제한 사항

 - 현재 유저 피로도 k는 1 이상, 5,000 이하 자연수

 - 던전의 정보가 담겨있는 dungeons는 행 길이는 1 이상 8 이하, 열 길이는 2

 - dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"]

 - 최소 필요 피로도와 소모 피로도는 1 이상 1,000 이하 자연수이며 최소 필요 피로도는 항상 소모 피로도보다 크거나 같음

---

2.구현

2-1. 풀이

던전의 개수가 8개이므로, 완전탐색으로 풀어도 충분히 시간이 남을 것이다. DFS 재귀 방식으로 진행하였다. 

2-2. 코드

#include <string>
#include <vector>

#define MAX_DUNGEONGS_COUNT 8
using namespace std;

vector<bool> visited(MAX_DUNGEONGS_COUNT);
int answer = 0;

void DFS(int depth, int k, vector<vector<int>> dungeons) {
    for (int index = 0; index < dungeons.size(); index++) {
        if (visited[index]) continue;
        
        if (dungeons[index][0] <= k) {
            visited[index] = true;
            DFS(depth + 1, k - dungeons[index][1], dungeons);
            visited[index] = false;
        }
    }
    
    if (answer <= depth) answer = depth;
    
}
int solution(int k, vector<vector<int>> dungeons) {
    DFS(0, k, dungeons);
    return answer;
}