[C++] Programmers Lv. 2 "피로도"

🔵 문제 링크

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

프로그래머스

 

🔵 문제 접근

문제에서 제시된 던전의 최대 개수는 8이므로 매우 적다.

따라서 던전을 입장하는 모든 순서를 탐색해 풀이할 수 있다.

백트래킹으로 풀이하였다.

 

🔵 전체 코드

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

// 최소 피로도 , 소모 피로도
// 최대한 많은 던전을 탐험하기
// 던전의 개수 최대 1 ~ 8 (매우 작음)

int ans;
bool visited[8];

void backtracking(int stamina, const vector<vector<int>>& dungeons, int count)
{
    // 던전을 들어간 순간 카운팅
    ans = max(ans, count);

    // 던전을 방문하는 모든 조합을 탐색 
    for (int i = 0; i < dungeons.size(); i++)
    {
        int require = dungeons[i][0];
        int use = dungeons[i][1];

        if (require <= stamina && visited[i] == false)
        {
            visited[i] = true;
            backtracking(stamina - use, dungeons, count + 1);
            visited[i] = false;
        }
    }
}


int solution(int k, vector<vector<int>> dungeons) 
{
    vector<bool> visited(dungeons.size(), false);
    backtracking(k, dungeons, 0);

    return ans;
}

 

🔵 시간 복잡도

던전의 개수를 N이라 할 때, 최악의 경우 모든 경로를 탐색하므로 시간 복잡도는 O(N!)이다.

하지만 실제로는 for문 안의 if 조건(유망 함수)에 따라 걸러지므로 훨씬 적게 연산한다.