피로도

문제 링크

문제설명

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

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

문제풀이

이 문제의 카테고리가 완전탐색으로 되어있으니 완전탐색으로 풀어보자

python에는 리스트들에서 원하는 개수만큼을 랜덤으로 뽑아올 수 있는
기본 함수들이 있다. (itertools.permutations / itertools.combinations)
이 문제에선 어떤 던전을 먼저 도는지 순서가 필요하므로 permutations를 쓰기로 한다

그 후 매 순열마다 remain(피로도)과 result(총 던전 탐험 횟수)를 초기화해주고,
던전을 돌 수 있는 경우마다 피로도를 차감하고, 탐험 횟수에 +1 해준다.

for l in permutations(dungeons, len(dungeons)):
	remain, result = k, 0
    for a,b in l:
        if(remain >= a):
            remain -= b
            result += 1

그 후 각각에 순열들에서 나온 result중 가장 큰 값을 return해주면 된다.

from itertools import permutations
def solution(k, dungeons):
    answers = []
    for l in permutations(dungeons, len(dungeons)):
        remain, result = k, 0
        for a,b in l:
            if(remain >= a):
                remain -= b
                result += 1
        answers.append(result)
    return max(answers)

P.S. 재귀함수로도 구현할 수 있다.

from copy import deepcopy
def solution(k, dungeons, n=0):
    if len(dungeons) == 0: return n
    answers = []
    for i in range(len(dungeons)):
        _dungeons = deepcopy(dungeons)
        x = _dungeons.pop(i)
        require, spend = x
        answers.append(solution(k-spend, _dungeons, n+1 if (k >= require) else n))
    return max(answers)

정답 코드

전체 코드 보기

# permutations를 이용한 풀이
from itertools import permutations
def solution(k, dungeons):
    answers = []
    for l in permutations(dungeons, len(dungeons)):
        remain, result = k, 0
        for a,b in l:
            if(remain >= a):
                remain -= b
                result += 1
        answers.append(result)
    return max(answers)
    
# 재귀를 이용한 풀이
from copy import deepcopy
def solution(k, dungeons, n=0):
    if len(dungeons) == 0: return n
    answers = []
    for i in range(len(dungeons)):
        _dungeons = deepcopy(dungeons)
        x = _dungeons.pop(i)
        require, spend = x
        answers.append(solution(k-spend, _dungeons, n+1 if (k >= require) else n))
    return max(answers)