[프로그래머스] 피로도 C++ 풀이

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

프로그래머스

 

 

풀이 방법

던전을 방문할 때 피로도가 감소된다.

즉, 던전의 방문 순서에 따라 추후의 방문의 선택지에 영향을 끼친다는 것이다.

순열을 구현하여 던전이 방문이 가능하다면 방문하는 방식으로 구현하면 된다.

던전의 방문 순서가 중요하기에 조합이 아닌 순열 방식으로 구현해야 한다.

 

전체 코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
void sol(int k, vector<vector<int>> dungeons, int cnt, bool* visit, int* answer){
    
    for(int i=0; i<dungeons.size(); i++){
        if(visit[i]==false && k>=dungeons[i][0]){ // 입장이 가능하다면
            visit[i]=true; // 방문 표시
            
            // 방문 횟수 + 1이 현재까지 최대 방문 횟수보다 크다면 갱신
            *answer=max(*answer, cnt+1);

            // 소모피로도를 빼주고 cnt+1
            sol(k-dungeons[i][1], dungeons, cnt+1, visit, answer);
            visit[i]=false; // 방문 표시 해제
        }
    }

}


int solution(int k, vector<vector<int>> dungeons) {
    int answer = 0;
    bool visit[8]; // 방문한 던전
    fill(visit, visit+8, false);
    
    //남은 피로도, 던전, 탐험한 던전 횟수, 방문 여부 배열, 최대 방문 횟수
    sol(k, dungeons, 0, &visit[0], &answer);
    return answer;
}