Algorithms / Programmers / 타겟 넘버

링크

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

풀이

dfs를 이용해 풀면 된다.
target에 numbers에 있는 숫자를 더하거나 빼기를 하다보면 전체 numbers의 길이가 0이 나올때가 있다. 그때 target의 값이 0이면 타겟과 일치하는 경우 이므로 이때 1을 리턴해줘서 answer변수에 1씩 증가하도록 했다.
numbers가 [1,1,1,1,1] 그리고 target이 3일때 컴퓨터가 계산하는 순서는 대충 아래와 같다(일부만 적음).
이진법 보는거같음, 신기하다.

+1+1+1+1+1 = 5 -> return 0
+1+1+1+1-1 = 3 -> return 1
+1+1+1-1+1 = 3 -> return 1
+1+1+1-1-1 = 1 -> return 0
+1+1-1+1+1 = 3 -> return 1
+1+1-1+1-1 = 1 -> return 0
+1+1-1-1+1 = 1 -> return 0
+1+1-1-1-1 = -1 -> return 0

코드

def dfs(numbers, target):
    if len(numbers)==0 and target==0:
        return 1
    elif len(numbers)==0:
        return 0
    else:
        res = 0
        res += dfs(numbers[:-1], target+numbers[-1])
        res += dfs(numbers[:-1], target-numbers[-1])
        #This return here cannot affect to answer variable since
        #the len(numbers) is not zero.
        #It only memorizes the last calculated number.
        return res
    
def solution(numbers, target):
    answer = dfs(numbers, target)
    return answer