[C++][Programmers][완전탐색] 피로도

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

프로그래머스

 

[해결책]

1) 던전 개수가 최대 8개라서 permutation으로 순서 조합 뽑고 탐색하며 최대 탐험 개수를 구하면 된다.

2) permutation말고도 DFS로도 풀 수 있다.

 

[알아둘 것]

* DFS/BFS Algorithm 및 구현법

[Algorithm][C++] BFS/DFS

 

* C#의 foreach문 같은 for문 사용법

vector<int> v = {1,2,3};

for(const auto& vValue: v){
	cout << vValue; // 1, 2, 3
}

 

[코드]

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(int k, vector<vector<int>> dungeons) {
    int answer = -1;

    //1. 조합 돌리기 쉽게 오름차순 정렬
    sort(dungeons.begin(), dungeons.end());
    
    //2. 조합 순서대로 탐색하며 최대 던전 탐색 가능 수 구하기.
    do{
        int count = 0;   
        int currentEnergy = k;
        for(const auto& dungeon: dungeons){
            int minEnergy = dungeon[0];
            int useEnergy = dungeon[1];
            if(minEnergy <= currentEnergy){
                currentEnergy -= useEnergy;
                count++;
            }
            else break;
        }
        answer = max(count, answer);
    }while(next_permutation(dungeons.begin(), dungeons.end()));
        
    return answer;
}

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

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

void DFS(int currentEnergy, int count, vector<vector<int>> dungeons){
    //현재 Energy가 0 이하면 바로 return해서 시간줄이기
    if(currentEnergy <= 0){
        return;
    }
    for(int i = 0; i < dungeons.size(); i++){
        int minEnergy = dungeons[i][0];
        int useEnergy = dungeons[i][1];
        if(!isVisited[i] && currentEnergy >= minEnergy){
            //해당 가지에선 더이상 탐색을 안하기 위해 방문 true 처리
            isVisited[i] = true;
            //다음 깊이로 DFS 탐색
            DFS(currentEnergy-useEnergy, count+1, dungeons);
            //리턴시 재탐색을 위해 방문 false처리
            isVisited[i] = false;
        }
    }
    answer = max(answer, count);
}

int solution(int currentEnergy, vector<vector<int>> dungeons) {    
    //현재 에너지 값과 탐색 깊이 값, dungeons 벡터를 넘김 
    DFS(currentEnergy, 0, dungeons);
    return answer;
}