타겟 넘버 - 프로그래머스 Python

문제: 
문제 설명
n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한 사항:
주어지는 숫자의 개수는 2개 이상 20개 이하입니다.각 숫자는 1 이상 50 이하인 자연수입니다.타겟 넘버는 1 이상 1000 이하인 자연수입니다.

 

 

생각해 볼 점 
1. 경우의 수 중에서 합했을 때 k 가 되는 경우 세기 →  DFS
2. 파이썬은 1000까지 재귀 가능. n < 1000 이니 더더욱 DFS 

 

내 풀이: 

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

dfs 를 solution 안에 적어도 된다! 이렇게 하면 numbers, target을 매개변수로 넘길 필요가 없다. 

그리고 밖에 있는 sum 변수를 함수 내에서도 변화시키고 싶으면 nonlocal 선언해주고 쓰면 된다. 

(사실 sum 이라고 변수명 짓는거 ... 좋지 않다. sum 함수랑 이름이 똑같아서 나중에 sum() 쓰고 싶을 때 못 씀... 이제 나도 슬슬 count 로 바꿔야지... 그치만 sum이 편해..) 

 

더 나은 다른 사람 풀이: 

출처: https://school.programmers.co.kr/learn/courses/30/lessons/43165/solution_groups?language=python3

프로그래머스

def solution(numbers, target):
    if not numbers and target == 0 :
        return 1
    elif not numbers:
        return 0
    else:
        return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])

이거 보고 살짝 기절함...