프로그래머스 lv 2. 87946 피로도 c++

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

#include <bits/stdc++.h>

using namespace std;

int solution(int k, vector<vector<int>> dungeons) {
    int answer = -1;
    vector<int> temp;
    for(int i=0; i<dungeons.size(); i++){
        temp.push_back(i);
    }
    do{
        int tmp=0;
        int tmpk=k;
        for(auto c: temp){ //이때 c 는 0 , 1, 2, 등의 수
            if(tmpk>=dungeons[c][0]){
                tmpk-=dungeons[c][1];
                tmp++;
                if(tmp==dungeons.size()) return tmp;
            } 
        }
        answer=max(answer,tmp);
    }while(next_permutation(temp.begin(),temp.end()));
    
    return answer;
}

next_permutation을 이용해서 경우의 수들을 모두 따라가면서 각각의 경우별로 던전을 도는 형태로 작성하였다. 

코드에 사용된 변수들의 이름을 지은것들이 조금 마음에 안들긴 하지만 딱히 생각나지 않아서 위와 같이 작성하였다. 

각 케이스별로 k값들이 새로, 그리고 그때의 최대 던전 돌 수 있는 횟수 저장 변수도 새로 만들어서 그 값들을 answer에 갱신해주는 형태로 작성하였다. 

완전탐색에서 모든 경우의 수들을 따져볼때, 순서를 바꾸어가면서 따지는 경우 next_permutation을 잘 떠올려서 사용해보도록 하자. 

 

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

using namespace std;

int answer = 0;
vector<vector<int>> dungeons;
int N;

int visit[8];
void dfs(int h, int p){
    if(answer < h)
        answer = h;

    for(int i=0; i<N; i++){
        if(visit[i] || dungeons[i][0] > p)
            continue;

        visit[i] = 1;
        dfs(h+1, p-dungeons[i][1]);
        visit[i] = 0;
    }
}

int solution(int k, vector<vector<int>> dungeons_) {
    dungeons = dungeons_;
    N = dungeons.size();

    dfs(0, k);

    return answer;
}

다른 사람의 풀이를 보니까 위와 같이 dfs 를 이용하는 풀이도 있었는데, 확실하게 위와 같이 한 차례씩 더 들어가면서 시행하는 형태의 문제의 경우는 dfs를 떠올릴만한 형태의 문제라고 생각된다. 아직 dfs를 사용하는것이 더욱 익숙하지 않은 모양이다. 

dfs, bfs등을 더욱 익숙하게 사용해보도록 하자. 일부러 떠올려서라도 문제에 적용해보자.