[프로그래머스/C++]Lv.2 - 피로도

문제 링크

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

시도한 방법

문제 잘못보고 주어진 피로도로 가능한 가장 높은 횟수를 구했었다.
아직도 재귀에 약한것 같다.

다른 사람의 풀이

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

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

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

using namespace std;

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

다른 사람의 풀이 해석

방문 체크용 bool 배열을 선언해두고 answer도 전역변수로 선언해둔다.
dfs알고리즘을 활용하였다.
count가 answer보다 크다면 answer를 갱신해준다.
for문을 활용해서 0번인덱스부터 visited와 현재 피로도를 검사해서 방문 가능하면
방문체크하고 다음 탐색을 시작한다. 탐색이 끝나면 다시 탐색할수있도록 visited를 초기화해준다.