[Programmers] 피로도

피로도

피로도를 클릭하면 바로 이동한다.

던전의 최대 개수가 8개이기 때문에 순열을 통해 완전탐색하면 답을 구할 수 있다.

다른 방법으로는 답을 구할 수 없을까 한참 생각해봤는데 정말 없다!

그럼 던전 개수가 1000개만 주어져도 1000! 개수의 순열을 탐색해야하는데..

더 효율적인 방법은 없는건가?

---

from itertools import permutations


def solution(k, dungeons):
    answer = float('-inf')

    # 1. 방문 할 던전 순열 구하기
    for permutations_dungeons in permutations(dungeons):
        cur_tired = k
        tmp_answer = 0
        for dungeon in permutations_dungeons:
            min_tired = dungeon[0]
            use_tired = dungeon[1]
            # 2. 현재 피로도가 최소 요구 피로도 이상이라면 던전 탐험
            if min_tired <= cur_tired:
                cur_tired -= use_tired
                tmp_answer += 1
        answer = max(tmp_answer, answer)

    return answer


if __name__ == "__main__":
    k = 80
    dungeons = [[80, 20], [50, 40], [30, 10]]

    print(solution(k, dungeons))