프로그래머스 피로도 완전탐색

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

프로그래머스

 

• 던전 방문 순서의 모든 조합을 구해야하므로 itertools의 permutations 메소드를 이용해서 완전 탐색해준다.

 

from itertools import permutations
def solution(k, dungeons):
    answer = -1
    result = []
    
    for n_dungeons in permutations(dungeons): 
        cnt = 0
        power = k
        for i in range(0, len(dungeons)):
            if n_dungeons[i][0] <= power and n_dungeons[i][1] <= power:
                power -= n_dungeons[i][1]
                cnt += 1
        result.append(cnt)
    
    answer = max(result)
    
    return answer

from itertools import permutations
def solution(k, dungeons):
    answer = 0
    
    for n_dungeons in permutations(dungeons): 
        cnt = 0
        power = k
        for i in range(0, len(dungeons)):
            if n_dungeons[i][0] <= power and n_dungeons[i][1] <= power:
                power -= n_dungeons[i][1]
                cnt += 1
        if cnt > answer:
            answer = cnt
    
    return answer

 

• 백트랙이라고 하는 것 같은데 dfs로 이 문제를 풀 때 dfs를 재귀호출하고 다시 visited 값을 초기화해주는 방법이다
• 결과적으로 permutations 함수를 쓴 것과 같이 모든 조합에 대해서 방문하게 된다

 

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