[프로그래머스] 피로도

문제 링크:

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

회고:

• 무식하게 완전 탐색하는 brute force 유형의 문제.
• brute force의 대표적인 알고리즘 유형으로는 dfs와 bfs가 있다.
• 한 놈부터 조지고(?)보는 dfs로 탐색하기에 적합한 문제.
  
  

python

max_cnt = 0


def dfs(k: int, dungeons: list, visited: list, cnt: int):
    global max_cnt
    max_cnt = max(max_cnt, cnt)

    if max_cnt == len(dungeons):
        return

    for i in range(len(dungeons)):
        if not visited[i] and dungeons[i][0] <= k:
            visited[i] = True
            dfs(k - dungeons[i][1], dungeons, visited, cnt + 1)
            visited[i] = False


def solution(k, dungeons):
    global max_cnt
    visited = [False] * len(dungeons)

    dfs(k, dungeons, visited, 0)
    return max_cnt


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

    print(result)
    print(result == 3)

3
True