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

https://programmers.co.kr/learn/courses/30/lessons/87946?language=cpp# 

코딩테스트 연습 - 피로도

 

1. 서론

 

처음엔 눈치채지 못했지만 직관적인 순열 문제이다.

 

2. 문제 풀이

 

어떤 게임에 피로도 시스템이라는 게 있다. 던전 하나를 돌 때 유저가 가지고 있어야 하는 최소 피로도가 있고, 던전을 돌았을 때 소모 피로도가 있다. 하루에 탐험할 수 있는 던전이 여러 개 있는데 최대한 많은 던전을 도는 경우의 수를 구하는 문제이다.

 

처음에는 최소 피로도에 초점을 맞춰야 하나 소모 피로도에 초점을 맞춰야 하나 고민하다가 경우의 수를 구하는 문제임을 깨닫고 순열이라는 것을 깨달았다. 던전을 도는 순서가 어떠냐에 따라서 던전을 더 돌고 아니고 가 정해지기 때문에 순열로 푸는 문제이다.

 

순열 코드는 이 블로그를 참조했다.

출처: https://ansohxxn.github.io/algorithm/permutation/

(C++) 순열(Permutation) 구현하기

 

그래서 순열로 주어진 데이터의 경우의 수를 뽑아내는데 그 순서대로 던전을 돌았을 때 던전을 총 몇 번 돌 수 있는지를 배열에 저장한다. 그리고 그중 가장 큰 수를 골라 답으로 return 했다.

 

3. 코드 설명

 

#include <vector>
#include <algorithm>

using namespace std;

vector<int> x;

void swap(vector<int> &a, vector<int> &b)
{
    vector<int> temp = a;
    a = b;
    b = temp;
}
void permutation(vector<vector<int>> data, int depth, int n, int r, int k)
{
    if (depth == r)
    {
        int answer = 0;
        for (int i = 0; i < data.size(); i++)
        {
            if (data[i][0] <= k)
            {
                k -= data[i][1];
                answer++;
            }
        }
        
        x.push_back(answer);
        return;
    }
    for (int i = depth; i < n; i++)
    {
        swap(data[depth], data[i]);
        permutation(data, depth + 1, n, r, k);
        swap(data[depth], data[i]);
    }
}

int solution(int k, vector<vector<int>> dungeons) {
    
    permutation(dungeons, 0, dungeons.size(), dungeons.size() - 1, k);
    sort(x.rbegin(), x.rend());
    
    return x[0];
}

 

던전의 피로도가 담겨있는 data 배열을 받아서 permutation 메서드에서 순열을 처리해준다.

n개의 던전을 n번 방문하는데 그 순서에 따라서 몇 번을 갈 수 있는지 달라지기 때문에 순서가 정해졌을 때 피로도를 계산해서 몇 개의 던전을 돌 수 있는지 순서 별로 값을 벡터 x에 값을 저장해줬다. 그리고 permutation 메서드가 처리를 끝내고 나면 x를 역순으로 정렬해서 가장 큰 값이 앞에 오게 한 후 가장 큰 값인 0번째 배열을 답으로 return 해줬다.