프로그래머스 level 2- 타겟 넘버

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

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

 

# Idea

주어진 배열 numbers는 순서대로 더하거나 빼야하고, 이 과정을 그려보면 Tree로 표현됨을 알 수 있다.

: (Edge를 +or - 로 표현하고, 각 노드들을 결과 값으로 표현한다)

따라서 Tree를 끝까지 순회해서 결과가 Target과 같은 경우의 수를 구하면 되며, 이는 DFS로 풀릴 수 있다.

 

# 나의 풀이

def solution(numbers, target):
    answer = 0
    n=len(numbers)
    def dfs(idx,result):
        if idx==n: #끝에 다다르면 종료
            if result==target:
                nonlocal answer #함수 안의 변수를 사용하기 때문에 지역변수가 아님을 처리해줘야한다.
                answer+=1
            return
        dfs(idx+1,result-numbers[idx])
        dfs(idx+1,result+numbers[idx])
    
    dfs(0,0)    
    return answer

: numbers 안의 원소들을 모두 더하거나 뺄때까지 재귀를 진행하고, 이 결과가 target하고 같은 경우에는 answer의 경우의 수를 더했으며, 다른 경우에는 그냥 return하였다.

: tree가 끝에 다다르면 1+1+1+1+1, 1+1+1+1-1.. 등의 결과가 나오게 되고, 이 값을 target하고 비교하면 된다. 

 

+) 재귀/ 트리 순회 참고 포스팅

https://velog.io/@polynomeer/%EC%9E%AC%EA%B7%80Recursion

재귀(Recursion)