[PS, Algorithm] - 피로도 (프로그래머스 코딩테스트 연습, LEVEL 2)

📒문제

📌풀이

from itertools import permutations as permu

def solution(k, dungeons):
    cases = list(permu([i for i in range(0, len(dungeons))], len(dungeons)))
    result = -1
    
    for case in cases:
        health = k
        num = 0

        for t in case:
            req, use = dungeons[t][0], dungeons[t][1]

            if req > health: break
            
            health -= use
            num += 1
        
        if result < num: result = num

    return result
    

별로 안 어려웠다. 애초에 던전 개수도 최대 8개로 엄청 적어서 최적화 신경 안 써도 완전 탐색으로 풀 수 있겠다고 판단했다.

cases에는 순열 함수로 만든 리스트가 들어가는데, 이 번호들은 방문할 던전의 순서를 나열해 놓은 배열이다.

그 후 cases를 돌면서, 최소 필요 피로도와 소모 피로도를 고려하며 최대로 돌 수 있는 던전의 개수를 구한다.