[Programmers] 피로도

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

프로그래머스

 

---

 

문제 해결 과정

착안

최소 필요 피로도 또는 소모 피로도로 정렬을 통해 해결할 수 있는 방법이 마땅히 떠오르지 않고 던전 수가 크지 않으므로, 백트래킹(bactracking, 퇴각검색) 알고리즘에 기반하여 문제를 해결하고자 했다.

 

구현

백트래킹에 기반하여 문제를 해결하기 위해 던전의 방문 여부를 표시할 배열(played[])을 별도로 선언하여 활용하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <vector>

using namespace std;

int Count;

void Play(int k, const vector<vector<int>>& dungeons, bool* const played, int idx, int cnt)
{
    if (!played[idx] && k >= dungeons[idx][0])
    {
        played[idx] = true;
        for (int i = 0; i < dungeons.size(); i++)
            Play(k - dungeons[idx][1], dungeons, played, i, cnt + 1);
        played[idx] = false;
    }
    else
    {
        if (Count < cnt)
            Count = cnt;
    }
}

int solution(int k, vector<vector<int>> dungeons)
{
    for (int i = 0; i < dungeons.size(); i++)
    {
        bool played[8] = { 0, };
        Play(k, dungeons, played, i, 0);
    }    
    
    return Count;
}

 

실행 결과