문제 설명

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• k는 1 이상 5,000 이하인 자연수입니다.
• dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
  - dungeons의 가로(열) 길이는 2 입니다.
  - dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.
  - "최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
  - "최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
• 서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.

입출력 예

k	dungeons			result
80	[[80,20],[50,40],[30,10]]	3

입출력 예 설명

현재 피로도는 80입니다.

만약, 첫 번째 → 두 번째 → 세 번째 던전 순서로 탐험한다면

• 현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
• 남은 피로도는 60이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 20입니다.
• 남은 피로도는 20이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30입니다. 따라서 세 번째 던전은 탐험할 수 없습니다.

만약, 첫 번째 → 세 번째 → 두 번째 던전 순서로 탐험한다면

• 현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
• 남은 피로도는 60이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30이므로, 세 번째 던전을 탐험할 수 있습니다. 세 번째 던전의 "소모 피로도"는 10이므로, 던전을 탐험한 후 남은 피로도는 50입니다.
• 남은 피로도는 50이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 10입니다.

따라서 이 경우 세 던전을 모두 탐험할 수 있으며, 유저가 탐험할 수 있는 최대 던전 수는 3입니다.

접근 방법

처음에는 최소 필요 피로도와 소모 피로도 간의 규칙을 찾으려고 노력하였다. 나의 결론은 최소 필요 피로도와 소모 피로도의 차가 큰 순으로 던전을 입장하면 최대의 던전에 들어갈 수 있다였다. 그러나 3개의 테스트에서 통과하지 못하였고 결국은 모든 방법을 진행한 뒤에 던전 입장 횟수가 가장 많은 경우를 찾아내는 방법으로 진행하기로 하였다. permutations을 사용하여 던전의 조합을 모두 구하여 조합들을 모두 순회하며 입장 가능 횟수 중 가장 큰 값을 반환하였다.

• 정답을 저장하는 변수 answer에 0을 넣는다.
• dungeons을 dungeons의 개수를 모두 사용한 조합의 모든 경우를 per에 배열로 저장한다.
• per의 길이만큼 반복하는 i에 대한 for문을 돌린다.
  -> 입장 가능 횟수를 저장할 임시 변수 cnt를 0으로 정의한다.
  -> 임시 변수 tmp_k를 선언하고 매 반복마다 k로 초기화해준다.
  -> per[i]의 길이만큼 반복하는 j에 대한 for문을 돌린다.
  --> 만약 tmp_k가 per[i][j][0]보다 크거나 같다면 cnt를 1 증가시키고 tmp_k에서 per[i][j][1]을 빼준다.
  -> answer에 max(answer, cnt)의 반환값을 저장한다.
• answer를 반환한다.

solution.py

from itertools import permutations
def solution(k, dungeons):
    answer=0
    per=list(permutations(dungeons, len(dungeons)))
    for i in range(len(per)):
        cnt=0
        tmp_k=k
        for j in range(len(per[i])):
            if tmp_k>=per[i][j][0]:
                cnt+=1
                tmp_k-=per[i][j][1]
        answer=max(answer, cnt)
    return answer