[프로그래머스] 피로도 in Python

태그

#알고리즘 #프로그래머스
문제 링크

최소 피로도와 소모 피로도가 주어졌을 때 얼마나 많은 던전의 개수를 지날 수 있는지 묻는 문제였습니다.

처음에는 그리디인가 하고 접근했었고, 입력 값을 정렬한 후 문제에서 주어진 피로도 k가 0보다 작은 구간이 될때 끝내려고 했는데, 그건 아니었습니다. 그래서 음.. 이러면 완전 탐색 말고는 없을텐데를 생각했어요. 혹시나해서 문제 입력값을 다시 확인해보니 문제의 입력값이 던전 개수 최대 8개라는 것!

그래서 완전 탐색으로 문제를 접근했고 저는 back tracking으로 문제를 풀었습니다. 제가 작성한 코드는 다음과 같아요.

res = 0
def dfs(cnt, k, dungeons, visited):
    global res

    if k <= 0:
        return

    if cnt > res:
        res = cnt

    for i in range(len(dungeons)):
        if i not in visited and k >= dungeons[i][0]:
            visited.append(i)
            dfs(cnt+1, k - dungeons[i][1], dungeons, visited)
            visited.pop()
            
def solution(k, dungeons):
    visited = []
    dfs(0, k, dungeons, visited)
    return res

if __name__ == "__main__":
    print(solution(80, [[80,20],[50,40],[30,10]]))

사실 visited는 굳이 append()와 pop()을 해줄 이유는 없습니다. 그냥 visited 배열 만들고 방문 표시만 해주면 되는데, 생각난 김에 그냥 pop이랑 append를 했습니다. 어차피 시간 복잡도는 1이기 때문에.. 물론 if i not in visited and k >= dungeons[i][0]: 코드에서 시간 복잡도가 O(n)이 되기 때문에 수정할 부분이긴 합니다. visited를 배열로 바꾸는건 어렵지 않으니 패스!