[프로그래머스] 피로도 C++

 

1. 문제

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

유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

 

2. 코드

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

using namespace std;

//수열 next_permutation을 활용하여서 풀이
//경우의 수를 다 계산한 다음 차례로 검증함
int solution(int k, vector<vector<int>> dungeons) {
    int answer = 0;
    
    vector<int> v;
    // 0부터 던전 사이즈까지 벡터에 저장
	for(int i=0; i<dungeons.size(); i++){
		v.push_back(i);
	}
    
    do{
        int pirodo=k;
        int count=0;
		for(int i=0; i<v.size(); i++){
            if(pirodo>=dungeons[v[i]][0]){
                //피로도 차감 및 던전 갯수 올리기
                count++;
                pirodo-=dungeons[v[i]][1];
            }
		}
        answer=max(answer,count);
	}while(next_permutation(v.begin(),v.end()));
    
    return answer;
}

 

3. 해설

//수열 next_permutation을 활용하여서 풀이
//경우의 수를 다 계산한 다음 차례로 검증함
int solution(int k, vector<vector<int>> dungeons) {
    int answer = 0;
    
    vector<int> v;
    // 0부터 던전 사이즈까지 벡터에 저장
	for(int i=0; i<dungeons.size(); i++){
		v.push_back(i);
	}

 

경우의 수가 많지 않기에 완전 탐색을 통해 풀수 있는 문제이다.

정해진 배열에서 순서를 바꾸는 경우의 수를 구할 때는 수열을 사용해서 만들어준다.

먼저 0~ 던전의 갯수 까지의 배열을 만들어준다.

만약 던전의 갯수가 3이라면 [0,1,2] 가 만들어진다.

  do{
	int pirodo=k;
	int count=0;
	for(int i=0; i<v.size(); i++){
        	if(pirodo>=dungeons[v[i]][0]){
                //피로도 차감 및 던전 갯수 올리기
                count++;
                pirodo-=dungeons[v[i]][1];
            }
	}
    	answer=max(answer,count);
}while(next_permutation(v.begin(),v.end()));

만들어진 배열을 가지고 next_permutation() 함수를 통해서 수열의 경우의 수를 출력한다.

do while문을 통해 수열의 경우의 수를 받아올 때 피로도와 던전이 필요한 최소 피로도를 넘긴다면 던전을 클리어하도록 설계한다.

만약 최소 피로도를 넘기지 못하면 계산하지 않고 넘어간다.

계산이 끝난 후 만약 Count가 기존의 answer보다 클 경우 answer에 count 값을 삽입한다.