[프로그래머스] Level 2. 피로도

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

프로그래머스

 

해결 방법

완전탐색을 진행하다가, 조건에 맞지 않을 경우 되돌아오는 백트래킹을 사용하여 해결한다.

1. 1번 던전을 들어가려 해본다. 들어가진다면, play수를 올리고 visisted[1번던전] 을 true로 던진 뒤 다시 do_search()를 진행한다.
2. 이상태에서 들어갈 수 있는 던전을 찾아본다 (이미 플레이한 1번 던전을 제외한 나머지 던전을 찾는다) . 있다면 또  visited[2번던전]  = true로 바꾼 뒤 다시 do_search() 를 호출, 이를 반복한다.
3. 그러다가 에너지가 부족해서 못들어가는 경우가 생길 경우 (do_search()의 재귀가 끝날 경우) , visited[2번던전]  = false로 바꾸고 넘어간다. 
4. 이런식으로 play를 계산해보고, 나온 play중 max값을 찾는다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int energe = 0; //현재 남은 에너지
int answer = -1; //정답저장. 서치해서 나온 play중 가장 큰수를 저장할것.
vector<bool> visited; //플레이한 던전의 index를 저장.
vector<vector<int>> d; //dungeons

void do_search(int play){
    
    if(play>= d.size()) return;
    
    for(int i=0 ; i<d.size();i++){
        if(visited[i] || energe < d[i][0]) continue;
        
        visited[i] = true;
        energe -= d[i][1];
       
        answer = max(answer, play+1);    
        
        do_search(play+1);
        
        energe += d[i][1]; //이 던전을 플레이하지않았던것처럼 하고 다음으로 넘어감
        visited[i] = false;
    }
}

int solution(int k, vector<vector<int>> dungeons) {
    
    d = dungeons;
    visited.resize(dungeons.size(),false);
    energe = k;
    
    do_search(0);
    
    return answer;
}

 

마무리 하며

처음엔 정렬하여 문제를 해결할 수 있을까 했지만 어차피 visited 되지 않은 모든 던전을 새로 서치해야 했기 때문에, 정렬은 할 필요가 없었다. 이 문제는, 가능한 조합을 모두 찾되, 중간에서 더 불가능한 조건이 나오면(에너지부족) 더이상 찾지 않는 것이 핵심이다.

 

Level 3 에서 주사위선택하는 문제 못풀었던게 있는데, 이  문제의 심화버전이라는  생각이 들었다. 조만간 다시 도전해봐야겠다.