프로그래머스: 타겟 넘버

문제

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

 

문제 풀이

 현재 값을 더하느냐, 빼냐에 따라 2 가지로 나뉘게 된다. 이는 DFS를 통해 탐색할 경우 각 경우에 대해 판단할 수 있다. 각 노드 마다 2개의 가지로 뻣어나가게 되므로, 트리의 최대 depth(숫자의 수) 만큼 도달 하였을 때, 계산 된 값과 target과 일치하는지 확인하여 문제를 해결할 수 있다.

 

코드

def dfs(numbers, target, i = 0):
    answer = 0
    if i == len(numbers):
        if sum(numbers) == target:
            return 1
        return 0
    
    answer += dfs(numbers, target, i + 1)
    numbers[i] *= -1
    answer += dfs(numbers, target, i + 1)
    
    return answer


def solution(numbers, target):
    return dfs(numbers, target)