[C++][완전탐색] 프로그래머스 - 피로도

 

# 풀이

우선 던전의 최대 개수가 8개밖에 되지 않는다!

그냥 무식하게 for문을 돌려도 시간 초과가 나지는 않을 것 같았다.

 

우선 처음 생각해본 방법으로는,

1. next_permutation을 써서 던전 도는 순서의 순열을 생성하고

2. 그 순서대로 던전을 돌면서 최대값을 계속 갱신해 주는 것이다.

 

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

using namespace std;

int solution(int k, vector<vector<int>> dungeons) {
    int answer = -1;
    
    vector<int> idx;
    vector<vector<int> > idxTmp(8);
    for(int i=0; i<dungeons.size(); i++) {
        idx.push_back(i);
    }
    
    int i=0;
    do {
        vector<int> tmp;
        for (auto it = idx.begin(); it != idx.end(); ++it) {
            tmp.push_back(*it);
        }
        idxTmp.push_back(tmp);
        i++;
    } while(next_permutation(idx.begin(), idx.end()));
    
    for(int i=0; i<idxTmp.size(); i++) {
        int cnt = 0;
        int health = k;
        for(int j=0; j<idxTmp[i].size(); j++) {
            if(health >= dungeons[idxTmp[i][j]][0]) {
                cnt++;
                health -= dungeons[idxTmp[i][j]][1];
            }
        }
        answer = max(answer, cnt);
    }
    
    return answer;
}

 

아주 똥같은 코드가 나왔지만, 일단 성공은 했다...!

 

그런데 idxTmp를 꼭 만들 필요가 있나? 어차피 next_permutation을 쓰면 그냥 모든 순열이 나올텐데...?

심지어 총 개수만 구하면 되는데 나는 왜 이런 짓을 했지?

 

다시 풀어보자

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

using namespace std;

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

이렇게 간단한 것을 무슨 짓을 한걸까

 

#느낀점

문제를 풀면서 항상 느끼지만, 어렵게 꼬아서 생각하지 말자.

쉽게 생각하면 다 풀 수 있다.

머리로는 항상 알고 있는데 왜 문제만 보면 꼬아서 생각하게 될까....