Programmers - 피로도

---

title: Programmers - 피로도
date: 2022-06-25
tags:

• Algorithm
• DFS

---

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

문제 요약

현재 피로도, 그리고 던전에 들어가기 위한 최소 피로도와 소모 피로도가 주어진다. 유저가 탐험할 수 있는 최대 던전 수를 구하여 return한다.

문제 풀이

던전의 개수는 8개밖에 존재하지 않으며, 순서에 영향을 받으므로 DFS가 적합하다고 판단하였다.
DFS 함수의 최대 호출 횟수는 8! + 1(처음 진입시 1회) = 약 40k이다.
조건이 까다롭지 않으므로 .data 함수 없이 vector에 직접 접근하여도 문제가 없을 것 같다.

프로그램

#include <vector>
#include <algorithm>

using std :: vector ;

int iDungeonSize ;
bool brgUsed [ 8 ] ;
vector < int > * vpTemp ;

int iDFS ( int iCurrentTiredness )
{
    int iAnswer = 0 ;

    for ( int i = 0 ; i < iDungeonSize ; ++i )
    {
        if ( ( ! brgUsed [ i ] ) && ( vpTemp [ i ] [ 0 ] <= iCurrentTiredness ) )
        {
            brgUsed [ i ] = true ;
            iAnswer = std :: max ( iAnswer , iDFS ( iCurrentTiredness - vpTemp [ i ] [ 1 ] ) + 1 ) ;
            brgUsed [ i ] = false ;
        }
    }

    return iAnswer ;
}

int solution ( int k , vector < vector < int > > dungeons )
{
    int answer = -1 ;
    vpTemp = dungeons.data () ;
    iDungeonSize = dungeons.size () ;
    std :: fill ( brgUsed , brgUsed + iDungeonSize , false ) ;



    return iDFS ( k ) ;
}