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

 

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

 

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

프로그래머스

---

 

해결전략

 

DFS

완전 탐색

 

---

 

코드

 

#include <algorithm>
#include <string>
#include <vector>
using namespace std;
 
int maxCnt; // 방문 가능한 최대 던전 개수
int ch[8]; // 각 던전에 대한 방문 여부 체크 배열
 
// x: 현재 에너지, dungeons: 각각의 던전 정보 (에너지 요구량, 소모량), cnt: 현재까지 방문한 던전의 개수
void DFS(int x, vector<vector<int>>& dungeons, int cnt)
{    
    if (cnt > maxCnt) // 만약 현재까지 방문한 던전의 개수가 이전 최대치보다 크다면
        maxCnt = cnt; // 최대치 업데이트
    
    for (int i = 0; i < dungeons.size(); i++) // 모든 던전에 대해서 반복
    {   // 아직 방문하지 않은 던전이며, 현재 에너지가 해당 던전의 에너지 요구량보다 크거나 같다면
    	if (ch[i] == 0 && x >= dungeons[i][0]) {
            ch[i] = 1;
            DFS(x - dungeons[i][1], dungeons, cnt + 1);
            ch[i] = 0;
        }
    }
}
 
int solution(int k, vector<vector<int>> dungeons)
{
    DFS(k, dungeons, 0);
 
    int answer = maxCnt;
 
    return answer;
}

 

 

---