[프로그래머스/Python] - Lv2 / 피로도

피로도

level2-완전탐색-피로도

import itertools
def solution(k, dungeons):
    #피로도 k
    #각 던전별 최소 필요도, 소모 피로도 2차원 배열로 주어짐
    data = dungeons
    #유저가 탐험할 수 있는 최대 던전 수 리턴.
    n = len(data)
    res = 0
    temp = list(range(n))
    #던전의 개수가 8이하이니 순열로 하더라도 얼마 안걸림. 시간복잡도 여유.
    for e in itertools.permutations(temp, n):
        #e에 저장된 인덱스 순서로 탐험할 때...
        for i in range(n):
            p = k
            cnt = 0
            for idx in e:
                a,b = data[idx][0], data[idx][1]
                if p >= a:
                    p -= b
                    cnt += 1
            res = max(res, cnt)
    return res

코멘트

해당 문제는 던전의 개수가 8이하 이므로 시간복잡도가 여유 있다. 순열로 어떤 던전부터 탐색할지 모든 경우의 수에 대해 가능한 던전 탐험의 수를 구하면 된다.