[프로그래머스] 피로도 - c++

피로도

이 문제는 초기 설정이 c 로 되어있다.
그래서 문득.. 그저께 본 코테가 생각났다.

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

이런 헤더가 있고 그 뒤에 #include vector, iostream.. 등등을 추가해도 안 먹길래.. 일부러 막아둔줄 알았다 하지만 이 문제를 풀며 해당 문제점을 지피티한테 물어봤더니.. 기본적으로 c언어로 설정되어 있어서 그런 것이었다

그저께 코테 3문제 모두 c로 설정되어 있는 것을 c++로 안바꾸고 푼 것이었다..!

조심하자 🙃🙃..

앞으론 언어설정 잘 바꿨는지 조심하자 . ..

돌아돌아 가며 풀었는데 한 문제를 못풀었었다 ^ㅁ^
진짜 조심하자!!!!ㅠㅠ

---

[문제 정의]

아무튼 문제설명을 시작하겠다 !

문제 조건은 다음과 같다.

• 탐험을 위해 필요한 '최소 필요 피로도' >= 현재 피로도 여야 던전 탐험 가능
• 탐험을 마쳤을 때 소모되는 '소모 피로도'

<입출력 예>

k = 80, dungeons = [[80,20],[50,40],[30,10]], result = 3

이 문제에서 고려해야 할 점은 각 던전을 순차적으로 실행하면 안되고, 유저가 탐험할 수 있는 최대 던전수를 찾아야 하므로 각 던전을 탐험하는 모든 경우의 순서를 돌아가며 최대 던전수를 return 하는 것이다!

'최소 피로도'와 '소모 피로도' 를 쌍으로 묶은 needs 배열을 만들고, sort했다. (pair의 first를 기준으로 sort 되므로 최소 피로도 기준으로 정렬된다.)

그 후 모든 던전의 순서를 고려해야 하므로 next_permutation을 이용해 각 순서 별 최대 던전수를 업데이트하며 풀었다.

[전체 코드]

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

using namespace std;

int solution(int k, vector<vector<int>> dungeons) {
    int answer = -1;
    vector<pair<int, int>> needs;
    for(int i=0; i<dungeons.size(); i++) {
        needs.push_back({dungeons[i][0], dungeons[i][1]});
    }
    sort(needs.begin(), needs.end());
    
    do {
        int tmp_ans = 0;
        int tmp_k = k;
        for(int i=0; i<needs.size(); i++) {
            int needs_exp = needs[i].first;
            int somo_exp = needs[i].second;
            if (tmp_k >= needs_exp) {
                tmp_k -= somo_exp;
                tmp_ans++;
            }
        }
        answer = max(answer, tmp_ans);
    } while(next_permutation(needs.begin(), needs.end()));
        
    
    return answer;
}