[프로그래머스] 완전 범죄

완전 범죄

프로그래머스

 

• 내 풀이
  • DFS로 각 물건에 대해 A or B 도둑이 훔치는 경우를 모두 탐색.
  • 이미 방문한 (현재 물건, A누적, B누적) 상태는 visited 집합으로 중복 제거.
  • 모든 물건을 처리한 시점에 A, B의 흔적이 제한 미만이면 최소 A누적값 갱신.

def solution(info, n, m):
    l = len(info)
    answer = float('inf')
    visited = set()

    def dfs(cur, a, b):
        nonlocal answer

        if cur == l:
            if a < n and b < m:
                answer = min(answer, a)
            return

        key = (cur, a, b)
        if key in visited:
            return
        visited.add(key)

        if a + info[cur][0] < n:
            dfs(cur + 1, a + info[cur][0], b)

        if b + info[cur][1] < m:
            dfs(cur + 1, a, b + info[cur][1])

    dfs(0, 0, 0)

    return -1 if answer == float('inf') else answer