[프로그래머스] 피로도

프로그래머스: 링크

코딩테스트 연습 - 12주차

위클리 12주차 문제이다. 어려웠던 11주차 문제와 다르게 이거는 비교적 쉬웠다. 처음에는 Greedy로 풀기 위해 최소 필요 피로도 내림차순으로 정렬해야하나 고민했는데, 예시 문제를 보면 그 방식대로 풀면 문제가 해결되지 않았다. 문제 조건을 보면 던전 개수가 최대 8개이기 때문에 완전 탐색을 해도 큰 문제가 안된다고 판단했다.

그래서 DFS를 이용해 가능한 던전을 방문해보는 식으로 가능한 경우의 수를 모두 고려한다.

#include <string>
#include <vector>

using namespace std;
int visited[8] = {0};
int sz;
int answer = 0;
void dfs(int power, int cnt, vector<vector<int>> dungeons);
int solution(int k, vector<vector<int>> dungeons) {
    sz = dungeons.size();
    dfs(k, 0, dungeons);
    return answer;
}

void dfs(int power, int cnt, vector<vector<int>> dungeons){
    if(cnt > answer) answer = cnt;
    for(int i = 0;i < sz;i++){
        if(!visited[i] && dungeons[i][0] <= power){
            visited[i] = 1;
            dfs(power - dungeons[i][1], cnt + 1, dungeons);
            visited[i] = 0;
        }
    }
}