문제 설명

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 이하인 자연수입니다.

입출력 예

numbers		target	return
[1, 1, 1, 1, 1]	3	5

입출력 예 설명
문제에 나온 예와 같습니다.

접근 방법

DFS 깊이 우선 탐색 알고리즘을 활용하여 해결하였다. 사실 DFS가 익숙하지 않아서 조금씩 찾아보면서 구현하였고, 구현하고 보니 어렵지 않은 문제였다. 다음에 더할 인덱스를 next로 저장하고 만약 next가 numbers의 길이와 같다면 끝까지 검사한 것이기 때문에 이 경우에 결과값이 target과 같다면 답을 1 증가시키고 아니라면 그냥 return하도록 하였다. next가 numbers의 길이보다 작을 경우에는 첫번째 연산일 경우, 가장 첫번째 수가 -일수도 +일수도 있으므로 두 경우에 대해서 모든 경우를 dfs로 재귀호출하고, 첫번째 연산이 아닐 경우에는 지금까지 더해진 값에 -,+의 경우를 모두 재귀호출하는 방식으로 구현하였다.

• 답을 저장하는 변수 answer를 0으로 선언한다.
• dfs함수를 누적 값을 의미하는 num과 다음 인덱스를 나타내는 next를 인자로 하여 선언한다.
  -> answer변수를 그대로 사용하기 위해 answer 변수를 nonlocal선언해준다.
  -> 만약 next가 numbers의 길이와 같을 경우, (next는 다음 인덱스를 가리키므로 next==len(numbers)는 가장 마지막 검사를 마쳤다는 의미이다.)
  --> 만약 num이 target과 같다면 answer를 1 증가시킨다.
  --> 반환한다.
  -> numbers[0]이 -가 붙을 수도 있고, +가 붙을 수도 있으므로 이를 표현하기 위한 배열 sign을 선언하고 -num, num을 넣어준다.
  -> 만약 next가 1일 경우, (인덱스 0과 1 간의 연산일 경우)
  --> 2번 반복하는 i에 대한 for문을 돌린다.
  ---> dfs에 sign[i]+numbers[next], next+1을 넣어 재귀호출한다.
  ---> dfs에 sign[i]-numbers[next], next+1을 넣어 재귀호출한다.
  -> 그 외의 경우,
  ---> dfs에 num+numbers[next], next+1을 넣어 재귀호출한다.
  ---> dfs에 num-numbers[next], next+1을 넣어 재귀호출한다.
• dfs(numbers[0], 1)을 호출한다.
• answer를 반환한다.

solution.py

def solution(numbers, target):
    answer=0
    def dfs(num, next):
        nonlocal answer
        if next==len(numbers):
            if num==target:
                answer+=1
            return
        sign=[-num, num]
        if next==1:
            for i in range(2):
                dfs(sign[i]+numbers[next], next+1)
                dfs(sign[i]-numbers[next], next+1)
        else:
            dfs(num+numbers[next], next+1)
            dfs(num-numbers[next], next+1)
    dfs(numbers[0], 1)
    return answer