[프로그래머스] lv.2 피로도

 

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

프로그래머스

 

 

DFS

ans = 0
N = 0
v = []

def dfs(k, cnt, dungeons):
    global ans
    if cnt > ans:
        ans = cnt
    
    for j in range(N):
        if k >= dungeons[j][0] and v[j] == 0:
            v[j] = 1
            dfs(k-dungeons[j][1], cnt+1, dungeons)
            v[j] = 0
    

def solution(k, dungeons):
    global N, v
    N = len(dungeons)
    v = [0] * N
    dfs(k, 0, dungeons)
    return ans

 

다른 사람의 풀이

 

순열

import itertools
def solution(k, dungeons):
    answer = -1
    visited = 0
    for dungeon_permutations in itertools.permutations(dungeons):
        have, count = k, 0
        for need, cost in dungeon_permutations:
            if have >= need and have >= cost:
                have -= cost
                count += 1
        visited = max(visited, count)
    answer = visited
    return answer

lambda 

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])

 

lamdba 2

최소 필요 피로도와 소모 필요도로 우선순위를 만드는 방법인데

추가된 테스트케이스 18, 19번을 통과하지 못한다. 

최소 필요 필요도와  소모 필요도 비율이 같은 경우가 문제인데

k = 100, dungeons = [[80, 8], [90,9], [100,10]] 이면 3을 반환해야하는데

정렬 결과 [[80, 8], [90,9], [100,10]] 가 되고, 2를 반환한다.

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