프로그래머스(C++) - 피로도

●문제

 

●입출력

 

사용 알고리즘 : DFS, 백트래킹, 완전탐색

문제풀이 : dungeons에는 첫번째로 최소 필요 피로도, 두번째로 소모 피로도가 주어짐

k가 내가 가진 피로도, k현재피로도에서 최소 필요 피로도가 충족되면 던전을 사용가능

던전 사용뒤에는 소모 피로도를 깎음

 

푼방법 : DFS를 사용하여 재귀함수로 k - dungeons[i][1] 만큼 뺀뒤 클리어를 +1

백트래킹을 사용하여 방문여부를 관리

#include <string>
#include <vector>
#include <algorithm>

using namespace std;
int dfs(int k, vector<vector<int>> dungeons, vector<bool>visited, int clear)
{
    int result = clear;
    for (int i = 0; i < dungeons.size(); i++)
    {
        //이미 방문했거나 최소 피로도보다 작으면 스킵
        if (visited[i] || dungeons[i][0] > k) continue;
        //방문여부 체크
        visited[i] = true;

        //사용 피로도 감소후 다음 던전 체크 단 최대값 갱신
        result = max(dfs(k - dungeons[i][1], dungeons, visited, clear + 1), result);

        //백트래킹
        visited[i] = false;
    }
    return result;
}
int solution(int k, vector<vector<int>> dungeons) 
{
    vector<bool>visited(dungeons.size(), false);
    return dfs(k, dungeons, visited, 0);
}

 

 레벨 : 2

점수 : 1