[Algorithm] 프로그래머스 타겟 넘버 | 파이썬

※ 타겟 넘버

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

프로그래머스

 

문제 해결 TIP

DFS로 구현한다.

숫자 한 개에 대해 음수, 양수 2가지 경우의 수를 각각 뻗어나가며 모든 경우의 수 중에, 마지막 결과가 타겟과 같을 때 방법 하나를 추가하는 식으로 진행한다.

 

전체 코드

answer = 0
def dfs(numbers, target, result, idx):
    global answer
    # 깊이가 같고 마지막 결과가 타겟과 같을 때
    if idx == len(numbers):
        if result == target:
            answer+=1
            return answer
    # 깊이가 같지 않다면 다음 숫자의 음수, 양수 더하기
    else:
        dfs(numbers,target,result+numbers[idx],idx+1)
        dfs(numbers,target,result-numbers[idx],idx+1)
def solution(numbers, target):
    dfs(numbers,target,0,0)
    return answer