[Python] 피로도

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

프로그래머스

• 첫 번째 풀이(틀림)

def solution(k, dungeons):
    answer = 0
    t_list = [(i, x[0]-x[1]) for i, x in enumerate(dungeons)]
    t_list = sorted(t_list, key=lambda x : x[1], reverse=True)
    
    for i in t_list:
        
        if dungeons[i[0]][0] <= k:
            k -= dungeons[i[0]][1]
            answer += 1
    return answer

최소 필요 피로도와 소모 피로도의 차이가 큰 던전부터 돌면 되지 않을까? 하는 생각으로 풀었음.

3개의 테스트 케이스에서 틀림

뭔가 빼먹은 게 있었나...

 

• 두 번째 풀이(순열 이용)

from itertools import permutations

def solution(k, dungeons):
    answer = 0
    p_dun = list(permutations(dungeons))
    
    for i in p_dun:
        answer2 = 0
        t = k
        for j in i:
            if j[0] <= t:
                t -= j[1]
                answer2 += 1
        answer = max(answer, answer2)
        
    return answer

그냥 순열을 이용해서 가능한 모든 순서를 저장하고 각 경우의 수마다 던전수를 체크한 뒤에 최댓값을 리턴함

이게 옳았나?