[Python] 프로그래머스 - 타겟 넘버

https://programmers.co.kr/learn/courses/30/lessons/43165?language=python3 

코딩테스트 연습 - 타겟 넘버

무난한 DFS/BFS 문제이다.

 

def solution(numbers, target):
    global answer
    answer = 0
    cnt = 0
    dir = [-1, 1]  # 숫자를 더하거나 빼거나 둘 중 하나이므로 [-1, 1] 선언
    def dfs(cnt, k):
        global answer
        # k가 numbers의 길이와 같고(끝까지 더하거나 뺐을 때) cnt가 target과 같다면 answer 1증가
        if k == len(numbers):
            if cnt == target:
                answer += 1
        else:
            # tmp에 현재 cnt값에 numbers[k]를 더하거나 뺀 값을 넣고 dfs돌림
            for x in range(2):
                tmp = cnt
                tmp += numbers[k] * dir[x]
                dfs(tmp, k+1)
    
    dfs(0, 0)
    return answer

(프로그래머스 level: 2)