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

문제

---

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

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

 

 

 

풀이

---

def dfs(numbers,depth,num,target):
    global cnt
    if depth == len(numbers):
        if num == target : cnt+=1
        return
    
    dfs(numbers,depth+1,num+numbers[depth],target)
    dfs(numbers,depth+1,num-numbers[depth],target)

def solution(numbers, target):
    global cnt
    cnt=0
    dfs(numbers,0,0,target)
    
    return cnt

 

숫자마다 + 와 - 하는 방법이 있으므로 num+numbers[depth],num-numbers[depth]를 변수로 넘겨주면서 재귀 호출을 해준다.

 

재귀 반복 횟수(depth)가 numbers의 길이와 같아졌을때까지 재귀를 반복한다.

길이가 같을때 target과 값이 같다면 cnt를 증가시켜준다.