Dfs

프로그래머스 피로도 문제 바로가기 나의 풀이 First Thoughts 어떤 기준에 따라 sort하면 최적 방법을 찾을 수 있지 않을까? (e.g key = lambda x : x[1]) -> 실패 그냥 bruteforce로 모든 경우의 수에 대해서 다 따져보자! 이를 위해서 itertools에서 permutations을 불러와서 모든 경우의 수를 따져주었다. math.perm()과는 달리 모든 경우의 수를 보여줘서 각 요소의 내용을 다뤄야할 때에는 매우 편리하다. from itertools import permutations as p def solution(k, dungeons): ans = 0 for dg in p(dungeons): hp = k cnt = 0 for d in dg: if d[0] > hp: break hp -= d[1] cnt += 1 ans = max(cnt, ans) return ans DFS 을 이용한 풀이 전혀 상상도 하지 못했는데 DFS을 이용한 풀이도 가능했다. 키포인트는 visited[j]를 1로 지정했다가 다시 0으로 바꿔주는 작업! ...