[프로그래머스] 타겟 넘버 (level2, python)

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

프로그래머스

 

아이디어

DFS를 사용해서 풀었다. +와 - 두 가지 경우 밖에 없기 때문에 dfs(+했을 경우), dfs(-했을 경우) 이렇게 호출해주었다.

종료조건은 numbers에 값이 없을 때 타겟과 같으면 global answer을 하나 키워주고 return하고, 아니면 그냥 return 하도록 하였다.

 

함수를 작성할 때 i로 depth를 넘겨줄지(golbal로 numbers 리스트를 받고), numbers를 넘겨줄 지 고민했는데 직관적으로 작성하기 위해(효율성 테스트가 없어서 될 것 같았다) numbers를 넘겨주었다. (pop을 하기 때문에 deepcopy 필수!)

전체 코드

import copy
answer = 0
def solution(numbers, target):
    def dfs(now, numbers, target):
        global answer
        if len(numbers) == 0:
            if now == target: answer += 1
            return
        
        tmp_numbers = copy.deepcopy(numbers)
        tmp = tmp_numbers.pop(0)
        
        dfs(now + tmp, tmp_numbers, target)
        dfs(now - tmp, tmp_numbers, target)
        
    dfs(0, numbers, target)
    return answer