*** [프로그래머스 lv2] 피로도

문제 보기

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

프로그래머스

 

문제 해결

난 순열 조합으로 문제 풀이를 하였지만 백트래킹으로 푸는 방법도 있었다.

기업 코딩테스트에 많이 나오는 풀이법이라고 하니 꼭 알아두자.

 

 

소스 코드

from itertools import permutations
def solution(k, dungeons):
    answer = 0
    
    for per in permutations(dungeons, len(dungeons)):
        tmp_k = k
        count = 0
        for p in per:
            if tmp_k >= p[0]:
                tmp_k -= p[1]
                count += 1
        answer = max(answer, count)            
        
    
    return answer

 

 

 

- 백트래킹 풀이법

def solution(k, dungeons):
    global answer
    answer = 0
    
    n = len(dungeons)
    visited = [False] * n
    
    tmp_k = k

    def dfs(tmp_k, cnt):
        global answer
        if cnt > answer:
            answer = cnt
        for i in range(n):
            if tmp_k >= dungeons[i][0] and not visited[i]:
                visited[i] = True
                dfs(tmp_k - dungeons[i][1], cnt + 1)
                visited[i] = False

    dfs(k, 0)
    return answer