[프로그래머스] lv2 타겟 넘버_python

타겟 넘버.
ex)
numbers = [1, 1, 1, 1, 1], tartget = 3, return = 5

이때,

타겟 넘버

이와 같이 표현될 수 있다. index 0번부터 계속해서 빼고 더하는 동작을 반복하며, target에 맞는지 확인하는 작업을 해주면 된다.
dfs에서도 재귀를 사용하여 알고리즘을 짰다.

def solution(numbers, target):
    answer = 0
    n = len(numbers)

    def dfs(idx, rlt):
    	# index가 끝
        if idx == n:
        	# 결과와 target이 같을 때
            if rlt == target:
                nonlocal answer
                answer += 1
            return
        # 위 조건을 다 만족하지 못한다면 재귀
        else:
            dfs(idx+1, rlt+numbers[idx])
            dfs(idx+1, rlt-numbers[idx])
    dfs(0, 0)
    return answer

 

nonlocal

 이번 알고리즘을 풀며 nonlocal을 사용했다.
nonlocal은 지역변수가 아닌 변수를 사용할 때 선언해준다.

# out, in 시점에서 global
def out():
	# out 시점에서 local
    # in 시점에서 nonlocal
    def in():
    	# in 시점에서 local