[프로그래머스 고득점 kit] 피로도 c++ 풀이 (완전 탐색)

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

프로그래머스

 

 

 

이 문제의 경우, 언듯 보면 dp로 풀고 싶지만, 'ungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.' 에 주목해야한다. 이 말은, 곧 N=8이기에, 몇중 포문을 돌던, 몇번 반복하던, 답만 구하면 되고, 시간초과는 '절대' 발생하지 않는다.

그렇기에, dp를 찾을 생각을 배제하고, 모든 가능성을 dfs로 완전탐색했다. 매번 여태 찾은 개수, hp(남은 피로도)를 인자로 넘겨주며 재귀함수를 돌면 끝이다.

 

#include <string>
#include <vector>
#include<queue>
using namespace std;
int siz;
int visit[10000];
int mx=-98765;
vector<vector<int>> dg;
void per(int depth,int hp){
    if(mx<depth)
        mx=depth;
    for(int i=0;i<siz;i++){
        if(visit[i]||dg[i][0]>hp)continue;
        visit[i]=1;
        per(depth+1,hp-dg[i][1]);
        visit[i]=0;
    }
}

int solution(int k, vector<vector<int>> dungeons) {
    int answer = -1;
    dg=dungeons;
    siz=dungeons.size();
    per(0,k);
    answer=mx;
    return answer;
}