[DFS] 타겟 넘버

타겟 넘버

프로그래머스

 

 

• 내 풀이
  • 시간 복잡도를 고려해서 알고리즘의 방향을 바꿨다!!
    • 처음에는 중복순열인가..? +, - 를 중복 순열로 가능한 모든 경우를 숫자에 붙여가면서 eval()을 사용해서 계산해야하나 고민하다가
    • 그렇다면 앞의 계산을 기억해야하는데... 하다가 dfs가 번뜩 떠올랐다
  • +,- 해가면서 계산 한 후 target값과 같아지는 경우만 체크
  • 2^20 = 1,048,576 (약 100만 번) 정도라 터지지 X → 2^30 (10억 번) 부턴 터짐 

def 밖에서 answer을 정의해준 후에 global로 불러와서 사용해야 한다

answer=0
def solution(numbers, target):
    global answer
    
    def dfs(idx, tmp):
        global answer
        if idx==len(numbers):
            if tmp==target:
                answer+=1
            return
        
        dfs(idx+1, tmp+numbers[idx])
        dfs(idx+1, tmp-numbers[idx])
           
    dfs(0,0)
    
    return answer