[C++] 프로그래머스 - 피로도 (Lv.2)

문제 설명

 

생각하기

또 다시 next_permutation으로 해결했다. next_permutation 만세만세

 

만약 예시처럼 3가지 던전 1, 2, 3이 있다면

1->2->3,

1->3->2,

2->1->3,

2->3->1, 

3->1->2,

3->2->1

이런식으로 순서를 다 고려해줘야 한다. (각 던전별로 최소필요피로도, 소모피로도가 다르니까)

그래서 순서를 정해주기 위한 벡터 arr을 생각해 냈다.

1. arr 벡터에 0부터 (dungeons 사이즈 - 1) 까지 숫자를 넣고
2. arr 벡터를 next_permutation을 하는데, 내부에서는
   1. for문으로 arr 벡터를 처음부터 끝까지 돌며(i), arr[i]에 있는 순서를 k라고 하면,
      1. 현재 유저 피로도가 dungeons[k][0]보다 크거나 같고 dungeons[k][1]보다도 크거나 같다면
         1. 현재 조합에서의 count 증가,
         2. dungeons[k][1]만큼의 유저 피로도 깎기
      2. 그렇지 않다면
         1. break (이 케이스(현재 arr 벡터)는 여기까지가 최선인 케이스임)

이렇게 구현했다.

 

코드

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


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

처음에는 flag를 두고 현재 유저 피로도가 (dungeons[k][0]보다 크거나 같고 dungeons[k][1]보다 크거나 같지) 않다면,

flag=false로 만들어, answer=max(cnt, answer) 부분을 flag가 true일 때만 실행시켰다.

그렇게 짰더니 실패가 나왔다.

왜냐하면 중간에 끊기는게 중요한 게 아니라, 중간에 끊기더라도 제일 높은 cnt 값을 구하는 것이 목표이기 때문이다.