[완전탐색] 프로그래머스 level 2 피로도 (Python 파이썬)

💡문제 링크

프로그래머스

 

💡문제 분석 요약

던전이 여러 개가 있음(1~8개)

던전에 대한 정보는 [a, b]로 주어지는데, a는 최소 필요 피로도이고 b는 소모 피로도이다.

이 던전을 통과하려면 현재 피로도가 a 이상이어야 하고, 이 던전을 통과하면 피로도가 b만큼 깎인다.

던전들에 대한 정보가 리스트로 주어졌을 때, 그리고 현재 피로도가 정수로 주어졌을 때

던전의 순서를 잘 조합해서 통과할 수 있는 던전 개수의 최댓값을 구하는 문제   

 

💡알고리즘 설계

그냥 무지성 순열 돌리기

from itertools import permutations
sort_list = permutations(dungeons)

 

💡코드

from itertools import permutations
def solution(k, dungeons):
    answer = -1
    sort_list = permutations(dungeons)
    for s in sort_list:
        ss = list(s)
        a, new_k = 0, k
        for i in range(len(dungeons)):
            if new_k >= ss[i][0]:
                a += 1
                # print(ss, "인 경우에", a, "개의 던전 통과")
                answer = max(answer, a)
                new_k -= ss[i][1]
            else:
                break
                
    return answer

 

💡 오답 풀이

처음에는 "최소필요피로도가 크고 소모피로도가 작을수록 앞에 온다."라는 개념을 이용해서 정렬해보려고 했다. 최소필요피로도가 큰 순서대로 정렬한 다음에 인덱스값을 점수로 주고, 소모피로도가 작은 순서대로 정렬한 다음에 인덱스값을 점수로 줬다.

이 방법으로 했는데 일부 테스트케이스에서 통과가 안 되었다. 47.4점..

아래의 케이스에서 걸렸다.

1. 던전 정보가 중복되는 경우(예. [[30, 10], [30, 10]]인 경우)

2. 점수가 중복되는 경우

그래서 그냥 무지성으로 permutations 순열로 풀었다 히히

 

💡 다른 풀이

solution = lambda k, d: max([solution(k - u, d[:i] + d[i+1:]) + 1 for i, (m, u) in enumerate(d) if k >= m] or [0])

갑자기 인생 살기 싫어지는 너무 간단한 식..

def solution(k, dungeons):
    answer = 0
    dungeons = sorted(dungeons, key = lambda x : ((x[1]+x[0])/x[0],x[1]))
    for x,y in dungeons:
        print("x :", x, "y : ", y)
        if k >= x:
            k -= y
            answer += 1
    return answer

내가 초반에 떠올렸던 "최소필요피로도가 크고 소모피로도가 작을수록 앞에 온다." 개념을 바탕으로 푼 다른 풀이도 있었다.

이걸 식으로 바꿔서 우선순위 = 최소필요피로도 / 소모피로도로 두면 최소필요피로도가 클수록, 소모피로도가 작을수록 우선순위가 커진다.

그런데 정렬할 때 우선순위가 높은 게 앞으로 오니까 이걸 역수로 치환해서 최소필요피로도 / 소모피로도로 두면 된다.

만약에 서로 다른 두 개 이상의 던전이 최소필요피로도 / 소모피로도값이 같다면? 소모피로도가 적은게 앞에 오도록 한다.

dungeons = sorted(dungeons, key = lambda x : ((x[1]+x[0])/x[0],x[1]))

정렬할 때 lambda를 써줬다.

근데 알고보니 테케18, 19에서 통과 못하네..

 

💡 느낀점 or 기억할정보

무지성 순열, 조합이 답일 때도 있다.

from itertools import combinations, permutations

꼭 기억해두자!