[프로그래머스] 피로도

dev-log·2021년 12월 4일
0
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int answer=0;
vector<vector<int>> used;
vector<vector<int>> dungeonsArray;
vector<bool> visited;
int dsize;
int dk;

void cal(){
    int temp=0;
    int tempK=dk;
    for(int i=0;i<dsize;i++){
        if(tempK>=used[i][0]){
             //if(dk-used[i][1]<0)
             //   continue;
            temp++;
            tempK-=used[i][1];
        }
    }
    answer=max(temp,answer);
}
void dfs(int cnt){
     if(cnt==dsize){
         cal();
         return;
     }

    for(int i=0;i<dsize;i++){
        if(visited[i]) continue;
        visited[i]=true;
        used[cnt][0]=dungeonsArray[i][0];
        used[cnt][1]=dungeonsArray[i][1];
        dfs(cnt+1);
        visited[i]=false;
    }
}

int solution(int k, vector<vector<int>> dungeons) {

    dsize=dungeons.size();
    dk=k;
    used=dungeons;
    dungeonsArray=dungeons;
    for(int i=0;i<dsize;i++){
        visited.push_back(false);
    }
    dfs(0);
    return answer;
}

던전의 경우의 수가 많지 않아서 완전탐색으로 풀 수 있었던 문제
dk의 값을 빼버리면 다른 경우의 수 계산에서 오류가 났다.

int tempK=dk 

위의 문장으로 dk값을 유지해주니까 해결됐다.

profile
배운 걸 기록하는 곳입니다.

0개의 댓글