[프로그래머스] 피로도 - Python3

문제 설명

유저의 체력 k와 던전을 탐험하는 데에 요구되는 '최소 필요 피로도'와 던전 탐험에 소요되는 '소모 피로도'들이 2차원 리스트 형태로 주어질 때, 유저가 탐험할 수 있는 최대 던전 수를 구하는 문제

https://school.programmers.co.kr/learn/courses/30/lessons/87946

프로그래머스

• 알고리즘 분류 - 완전탐색(Brute Force)
• 난이도 - Level 2

---

접근 방법

탐험할 던전의 인덱스들의 순열을 구하고, 순열의 각 수열 순서대로 탐색해본다.

예) 던전 3개가 주어질 시 구해지는 순열

(0, 1, 2) => 첫번째 -> 두번째 -> 세번째 던전 순서대로 방문한다고 가정하고 탐색
(0, 2, 1)
(1, 0, 2)
(1, 2, 0)
(2, 0, 1)
(2, 1, 0)

---

답안 코드

from itertools import permutations

def solution(k, dungeons):
    answer = -1
    
    
    for v in permutations(list(range(len(dungeons))), len(dungeons)):
        tmp = k
        cnt = 0
        
        for i in v:
            if tmp >= dungeons[i][0] :
                tmp -= dungeons[i][1]
                cnt += 1
                if cnt > answer:
                    answer = cnt
            
    return answer