[프로그래머스/Lv2] 피로도

 

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

프로그래머스

 

 

#include <iostream>
#include <string>
#include <vector>
using namespace std;
bool visit[9];
vector<int> v;
int ans = -1;

int countDungeons(int tiredness, vector<vector<int>> d){
    int cnt = 0;
    for(int i=0; i<v.size(); i++){
        if(tiredness >= d[v[i]][0]){
            cnt++;
            tiredness -= d[v[i]][1];
        }else{
            break; //tiredness가 더 적으면 더이상 던전 들어갈 수 없음
        }
    }
    return cnt;
}

void BT(int cnt, int dungeon_num, int tiredness, vector<vector<int>> d){
    if(cnt == dungeon_num){
        ans = max(ans, countDungeons(tiredness, d));
        return;
    }
    for(int i=0; i<dungeon_num; i++){
        if(!visit[i]){
            visit[i] = true;
            v.push_back(i); //dungeons 벡터의 i번째 던전 추가
            BT(cnt+1, dungeon_num, tiredness, d);
            v.pop_back();
            visit[i] = false;
        }
    }
}

int solution(int k, vector<vector<int>> dungeons) {
    int answer = -1;
    int n = dungeons.size();
    BT(0, n, k, dungeons);
    answer = ans;
    return answer;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cout << solution(80, {{80,20}, {50,40}, {30,10}}) << '\n';
    return 0;
}

 

처음에는 이렇게 풀었다.

그런데 생각해보면 굳이 모든 경우의 수를 할게 아니라 작은 것부터 진행했으면 어땠을지...

작은 것부터 가면 갈 수 있는 던전이 늘어난다. 가능하면 첫 트라이에서 바로 끝낼 수 있다. 그리고 다음 수열은 전 문제를 풀면서 배웠던 next_permutation함수를 사용하면 편리하게 알아낼 수 있다..!!

 

 

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int solution(int k, vector<vector<int>> dungeons) {
    int answer = -1;
    sort(dungeons.begin(), dungeons.end());
    do{
        int tiredness = k;
        int cnt = 0;
        for(auto i:dungeons){
            if(tiredness >= i[0]){
                cnt++;
                tiredness -= i[1];
            }
        }
        answer = max(answer, cnt);
    }while(next_permutation(dungeons.begin(), dungeons.end()));
    return answer;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cout << solution(80, {{80,20}, {50,40}, {30,10}}) << '\n';
    return 0;
}

 

역시 정렬이 많이 사용된다!

다음부터는 꼭 정렬을.. 생각해보도록 하자~

+ next_permutation()함수도~^^