[코테] 탐색 - 피로도[프로그래머스]

문제

출처: 프로그래머스 - 피로도

풀이

주어진 던전들의 모든 순서들을 나열하는 경우의 수인 수열을 모두 구한 뒤, 수열을 처음부터 탐색하며 던전을 돌 수 있는 수를 세고 그 중 가장 큰 수를 반환하면 된다.
던전의 순서는 임의로 입장가능하며 입장 순서에 따라서 클리어가 가능한 던전의 개수가 달라지기 때문에 모든 던전의 순서들의 경우의 수를 itertools의 permutations(순열)을 통해서 모든 순열을 생성한다.(참고 : itertools)
생성된 순열의 경우의 수들을 반복문을 통해 탐색하면서 입장 가능한 피로도라면 던전을 돌고난 후에 소모 피로도를 주어진 피로도에서 차감하면 된다. 던전을 돌았다면 횟수를 업데이트하도록 한다.

코드

from itertools import permutations as pe
def solution(k, dungeons):
    n = len(dungeons)
    answer = 0
    # permutations(k, n) : 에서 'k'는 순열을 만들 객체이며, 'n'은 'k'개 중에서 'n'를 가지고 순열을 만드는 경우
    for per in pe(dungeons, n): #per에 순열의 순서대로 던전들이 반환된다.
        nk = k # 던전마다 피로도 초기화하여 확인
        cnt = 0
        for p in per:
            if nk >= p[0]:
                nk -= p[1]
                cnt += 1
                
        answer = max(answer, cnt) # 많이 돌 수 있는 던전을 구하는 문제이므로 큰 수를 담도록 한다.

    return answer


if __name__ == '__main__':
    k = 80
    dungeons = [[80,20],[50,40],[30,10]]
    print(solution(k, dungeons))