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

프로그래머스 코딩테스트 연습의 '타겟 넘버' 문제입니다.

깊이/너비 우선 탐색으로 분류 되어있으며, 재귀적으로 풀어볼 수 있습니다.

---

[문제]

• 문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/43165

 

[풀이]

numbers의 길이는 최대 20 입니다.

재귀적인 트리구조를 생각해볼 수 있습니다.

number의 첫번째 number가 -일 때와 +일 때를 각각 트리의 루트로 두고,

자식 노드도 마찬가지로, 다음 number가 -일 때 +일 때로 두고 지금까지 거친 노드의 합을 구해나갑니다.

그럼 마지막의 여러 리프노드에서 합이 target 값인지 아닌지 확인해 볼 수 있습니다.

 

numbers = [4,1,2,1], target = 4 인 경우를 도식화 해보았습니다.

위 그림처럼 마지막까지의 합이 target 값과 같은 경우만 세어주면 됩니다.

 

[python 구현]

def recursive(numbers, sum, target):
    if numbers == []:
        if sum == target:
            return 1
        else:
            return 0
    return recursive(numbers[1:], sum + numbers[0], target) + recursive(numbers[1:], sum - numbers[0], target)

def solution(numbers, target):
    return recursive(numbers, 0, target)

위 코드에 따르면 마지막으로 각 함수에서 리턴되는 값은 0과 2가 될 것이고 답은 2가 됩니다.

 

위처럼 총합을 구해가며 target과 같은지 확인해볼 수도 있고,

target 값에서 number를 없애주면서 마지막에 값이 0인지 확인해보는 방식으로 구현해볼 수도 있습니다.