프로그래머스(programmers) 타겟 넘버 python 정답[DFS 풀이]

프로그래머스(programmers) 타겟 넘버 python 정답[DFS 풀이]

문제 링크

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

프로그래머스

문제 정답

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


def recur(numbers,target):
    if len(numbers) == 0 and target == 0 : return 1
    if len(numbers) == 0 and target != 0 : return 0
    return recur(numbers[:-1],target-numbers[-1]) + recur(numbers[:-1],target+numbers[-1])

문제 해설

dfs(재귀)를 이용한다

• target에 number의 마지막 요소를 더한 뒤, 배열을 조정하고 재귀 함수를 호출한다.
• target에 number의 마지막 요소를 뺀 뒤, 배열을 조정하고 재귀 함수를 호출한다.

각 노드는 양 쪽이 다 target을 만드는 데 성공하면 2, 하나만 만들면 1, 하나도 못만들면 0을 리턴하며,

구조적으로 바이너리 트리와 유사하게 된다.

따라서 시간복잡도는 2^n가 될 것이다.

(물론 총 함수의 호출 수는 등비급수가 될 테지만...)