[알고리즘] 프로그래머스 - 피로도 - 87946 파이썬 문제 풀이

문제 링크

문제

입출력 예시

조건

풀이 - 순열 + 조합

from itertools import permutations
from itertools import combinations
def solution(k, dungeons):
    table = []
    ans = 0
    for i in range(1, len(dungeons)+1):
        for j in combinations(dungeons, i):
            table.append(j)
    
    table.sort(key = lambda x: len(x), reverse=True)
    for arr in table:
        for j in permutations(arr, len(arr)):
            start_k = k
            count = 0
            for need, cur_k in j:
                if start_k >= need:
                    start_k -= cur_k
                    count += 1
            ans = max(count, ans)
        if ans != 0:
            break
    return ans

순열과 조합으로 모든 부분집합에 대해서 케이스를 정리하고 계산해주도록 했다. 그런데 생각해보니 굳이 조합을 해줄 필요가 없었다... 순열만 모든 케이스를 따져주면 어짜피 더 이상 던전에 입장을 못할 경우 걸러주기 때문이다... 그래서 아래에는 순열만 사용해서 풀어봤다.

풀이 - 순열

from itertools import permutations
def solution(k, dungeons):
    ans = 0
    for arr in permutations(range(len(dungeons))):
        start_k = k
        count = 0
        for i in arr:
            need, cur_k = dungeons[i]
            if start_k >= need:
                start_k -= cur_k
                count += 1
        ans = max(count, ans)
    return ans

순열만 사용하는 풀이를 하다보니 굳이 값을 넣어서 할 필요 없이 인덱스의 순열로 해주는 것이 더 편할 것 같아서 인덱스로 순열을 만들도록 하고 모든 케이스들을 계산해주도록 했다.