(프로그래머스 c++)위클리 챌린지 12주차

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

코딩테스트 연습 - 12주차

 

 

제한 사항이 크지 않기 때문에 모든 경우의 수를 구해 답을 찾으면 된다.

조합을 위해 next_permutaion을 이용.

 

인덱스의 위치를 next_permutation()을 이용해 모든 경우의 수를 구하고,

for문을 통해 조합된 인덱스로 던전을 돈다.

이후, answer을 갱신해 나가면 끝!

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

using namespace std;


int solution(int k, vector<vector<int>> dungeons) {
    int answer = 0;
    int size = dungeons.size();
    vector<int> index(size, 0);
    
    for(int i = 1; i < size; i++){
        index[i] = i;
    }
    
    do{
        int newK = k;
        int result = 0;
        
        for(int i = 0; i < size; i++){
            if(newK >= dungeons[index[i]][0]){
                result++;
                newK -= dungeons[index[i]][1];
            }
        }
        
        answer = answer < result ? result : answer;
    }while(next_permutation(index.begin(), index.end()));
    
    return answer;
}