93. 피로도

[문제]

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

프로그래머스

 

 

[풀이]

1. 던전을 탐색할 수 있는 모든 조합을 구해주고( O(n!) )

2. 최대로 돌 수 있는 던전 개수를 구해준다.

 

from itertools import permutations
def solution(k, dungeons):
    max_cnt = 0
    if k >= sum(list(zip(*dungeons))[1]):
        max_cnt = len(dungeons)

    cnt_list = []
    for method in list(permutations(dungeons)):
        cnt = 0
        z = k
        for x, y in method:
            if z >= x:
                z -= y
                cnt += 1
        if cnt == max_cnt:
            return cnt
        cnt_list.append(cnt)

    result = max(cnt_list)
    return -1 if result == 0 else result

 

 

흑흑.. 나중에 삘받으면 DFS 다시 공부해야겠다