[programmers] 피로도

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

코딩테스트 연습 - 피로도

 

 

 

처음에는 쉽게 구할 수 있는 방법이 있지 않을까 했다.

예를 들어, 필요한 피로도와 소모하게 되는 피로도의 차가 가장 큰 값부터 방문하는 방식으로 -> 반 정도 실패(반은 가능하다는게 오히려 놀라움)

 

※빼박 완전 탐색이다. 순서까지 중요한 순열 문제!

from itertools import permutations

def solution(k, dungeons):
    answer = 0
    perm = permutations(dungeons)
    for p in perm:
        tmp = int(k)
        tmp_answer = 0
        
        for i in p:
            need, used = i[0],i[1]
            if tmp >= need:
                tmp -= used
                tmp_answer +=1
            else:
                break
        answer = max(answer, tmp_answer)
    return answer

순열 (Permutations) 구하는 쌍의 순서가 고려된다 (n!)

조합 (Combinations) 구하는 쌍의 순서는 상관 없다 (nCi = n*(n-1)*...(n-i) / i*(i-1)*...*2*1 )

 

순열과 조합을 쉽게 구하는 방법은 itertools을 사용하면 된다. -> 튜플 안에 요소들이 들어간 generator 가 반환된다.

 

완전탐색이라는 힌트를 얻자면, 우선 효율성 테스트 문제가 없고, 던전의 최대 개수가 8까지이다.