[프로그래머스] 피로도 - python

문제 유형 : 완전탐색 

level 2

 

코드

순열 풀이

from itertools import permutations

def solution(k, dungeons):

    all_dungeons = []
    for i in permutations(dungeons,len(dungeons)):
        all_dungeons.append(list(i))

    possible = []
    i = 0
    while i < len(all_dungeons):
        stamina = k
        count = 0
        for j in all_dungeons[i]:
            if stamina >= j[0]:
                stamina = stamina - j[1]
                count += 1
            elif stamina < j[0]:
                break

        possible.append(count) 
        i += 1        

    answer = max(possible)      
    return answer

 

dfs() 풀이

answer = 0
N = 0
visited = []

def dfs(k, cnt, dungeons):
    global answer
    if cnt > answer:
        answer = cnt

    for j in range(N):
        if k >= dungeons[j][0] and not visited[j]:
            visited[j] = 1
            dfs(k - dungeons[j][1], cnt + 1, dungeons)
            visited[j] = 0

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

 

아오 진짜 ㅋㅋ