[C++] 피로도

[문제]

코딩테스트 연습 - 피로도 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

[문제 풀이]

완전탐색을 이용해서 우선 (0,1,2), (0,2,1).... 의 벡터를 만들자.

그 후 해당 순서대로 dungeons을 방문할때 문제의 조건에 맞게 몇번을 최대 방문할 수 있는지를 체크하자.

그렇게 방문 가능한 최댓값을 answer로 마지막에 정하면 완료.

[회고]

완전탐색을 이용한 기본적인 문제. 문제를 보고 푸는데 까지 20분이 안 걸렸다. 문제 이해하는데 첨에 꼬인것만 제외하면 더 빨리 풀 수 있을듯.

[코드]

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

using namespace std;

//최대 던전 숫자 확인.

int max_answer = 0;
vector<vector<int> > dungeon;
vector<int> vec;
int visited[10];

void backTrack(int k){
    
    if(vec.size() == dungeon.size()){
        //가능한지 아닌지 확인하는 함수.
        int answer = 0;
        for(int i = 0; i<vec.size();i++){
            if(k >= dungeon[vec[i]][0]){
                k -= dungeon[vec[i]][1];
                answer++;
            }
        }
        max_answer = max(max_answer, answer);
        return;
    }
    
    for(int i = 0;i<dungeon.size();i++){
        if(visited[i] == 0){
            vec.push_back(i);
            visited[i] = 1;
            backTrack(k);
            visited[i] = 0;
            vec.pop_back();
        }
    }
    
    return;
}

int solution(int k, vector<vector<int>> dungeons) {
    int answer = 0;
    dungeon = dungeons;
    
    backTrack(k);
    answer = max_answer;
    return answer;
}