프로그래머스 - 피로도 (C++)

 

 

문제의 입력으로 현재 피로도 K와 던전의 정보 숫자 쌍이 주어진다.

던전의 정보, 숫자 쌍 중에 첫 번째 숫자는 입장시 요구되는 최소 피로도를 의미하며 두 번째 숫자는 소모 피로도를 의미한다. 

 

즉, 입력중 첫 번째 원소인 [[80, 20]] 을 기준으로 본다면 입장하기 위해서 현재 피로도는 최소 80이어야 하며, 입장시 20이 소모된다는 뜻이다.

 

피로도 조건에 따라 던전을 어떤 순서로 갔을 때 최대 몇 개까지 던전을 클리어할 수 있는가? 를 구하는 문제이다.

---

문제 풀이

 

이 문제는 그렇게 복잡한 알고리즘을 요구하는 문제는 아니고, 모든 경우의 수를 하나하나 비교해보는 문제이다.

핵심은 그 경우의 수를 어떻게 구하느냐인데, 여러 방식이 있겠지만 본인은 순열을 사용하였다.

 

먼저, 던전의 개수만큼의 벡터를 resize하여, 각 원소에 인덱스 저장하였다.

 

 

 

이렇게 저장해놓은 뒤, next_permutation 을 이용해서 모든 경우의 수를 탐색하며 결과를 추적하였다.

* next_permutation 이란?

벡터의 원소를 2개씩 Swap하며, 순열을 쉽게 구할 수 있도록 도와주는 함수이다.

사용하기 위해선 벡터의 원소를 오름차순으로 정렬해야 한다.

 

1 - 2 - 3로 정렬되어 있다면, next_Permutation을 1번 사용시

1 - 3 - 2 로 원소의 위치를 변경해준다.

 

이런 식으로, 내부 알고리즘에 따라 자료구조 내부의 원소를 Swap하며 순열을 하나씩 만들어준다.

반복하다,  3 - 2 - 1 의 꼴로 완전한 내림차순이 되어 Swap할게 없어지면 함수가 false를 반환한다. 

 

순열 배열의 값이 1 - 2 - 3 - 4 인 경우, 1번 던전 -> 2번 던전 -> 3번 던전 -> 4번 던전 순으로 시뮬레이션 하였고

1 - 3 - 2 - 4 인 경우,  1번 던전 -> 3번 던전 -> 2번 던전 -> 4번 던전의 순으로 순열 배열의 원소와 동일하게 시뮬레이션 하였다.

---

풀이 코드

std::vector<int> Nums(dungeons.size());

for(int i = 0; i < Nums.size(); i++)
{
    Nums[i] = i;
}

 

먼저, 배열의 값에 인덱스를 넣어주었다.

 int MaxDungeons = 0;
    
while(true)
{
    int NumOfDungeons = 0;
    int CopyK = k;

    for(int i = 0; i < Nums.size(); i++)
    {
        if(CopyK < dungeons[Nums[i]][0])
        {
            break;
        }
        else
        {
            CopyK -= dungeons[Nums[i]][1];
            NumOfDungeons++;
        }
    }

    MaxDungeons = std::max(MaxDungeons, NumOfDungeons);

    if(std::next_permutation(Nums.begin(), Nums.end()) == false)
    {
        break;
    }
}

 

이후는 위에서 설명한 것과 같다.

 

현재 피로도가 던전의 입장 피로도보다 낮다면 반복문을 즉시 중지하며,

현재 피로도가 던전의 입장 피로도보다 높거나 같다면 피로도를 소모한 뒤 NumOfDungeons를 증가시켰다.

(NumOfDungeons 는 클리어한 던전의 수이다.)

 

이후, MaxDungeons를 갱신한 뒤, next_permutation을 이용하여 다음 경우의 수로 배열의 값을 변경하여 주었다.

 

반복문이 끝난 뒤, MaxDungeons를 반환하면 끝이다.

결과

 

사실, 순열을 이용해서 모든 경우의 수를 탐색하는 것은 시간복잡도가 상당하다.

하지만, 해당 문제는 던전의 수가 최대 8개로 제한되어 있었기 때문에 이런 방법이 가능한 것이다.