[Lv 2] 피로도

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

프로그래머스

 

이 문제는 dfs를 통해 해결할 수 있다.

 

초기 k값이 주어질 때 dungeons 배열에 존재하는 던전의 최소 피로도가 k이하인 경우 던전을 돌 수 있고

이후 해결 할 수 있는 던전은 k - dungeons[i][0]인 것을 알 수 있다.

 

또한 주어진 배열을 순차적으로 도는 것이 아닌 1 - 3 - 2 순서로 던전을 해결할 경우 더 많은 던전을 깰 수 있다는 것도 알 수 있다.

따라서 (1번 던전, 2번 던전, 3번 던전)을 첫번째로 돌고

1번 던전을 돌 경우 (2번 던전, 3번 던전)을 두번째로 돌아야 한다는 것을 알 수 있다.

이때 던전을 중복해서 돌 수 없으므로 visited 배열을 사용해 이미 돈 던전을 채크한다.

 

#include <string>
#include <vector>

using namespace std;

bool visited[8] = {false, };
int answer = 0;

void dfs(int k, int cnt, vector<vector<int>> dungeons){
    answer = max(answer, cnt);
    for(int i = 0;i<dungeons.size(); i++){
        if(visited[i] == false && k >= dungeons[i][0]){
            visited[i] = true;
            dfs(k - dungeons[i][1] ,cnt + 1, dungeons);
            visited[i] = false;
        }
    }
}

int solution(int k, vector<vector<int>> dungeons) {
    answer = 0;
    
    dfs(k,0,dungeons);
    return answer;
}