타겟넘버

문제 설명

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. numbers에 있는 원소들을 + 하거나 - 했을 때 결과가 target과 같아야 하기 때문에 +, - 경우에 따른 queue를 만들어준다. → 초기에는 numbers의 첫 번째 원소(value)와 인덱스(index) 값을 대입한다.
2. queue에 있는 원소들을 pop하고 index는 1을 증가시켜준다.
3. 원소가 배열의 마지막 원소가 아니라면 queue에서 value값과 다음 인덱스 값을 +, -의 값을 각각 넣어준다.
   1. value가 numbers의 원소에 순서대로 접근하여 target을 찾기 때문에 다음 index로 접근하는 것이며 때문에 index의 값도 같이 queue에 넣어주면 좋다.
4. 만약 마지막 원소이고 value 값이 target 값과 같다면 answer에 1을 증가시켜준다.

# BFS
def solution(numbers, target):
    answer = 0
    queue = [[numbers[0],0], [-1*numbers[0], 0]]
    n = len(numbers)

    while queue:
        value, index = queue.pop()
        index += 1
        if index < n:
            queue.append([value + numbers[index], index])
            queue.append([value - numbers[index], index])
        else:
            if value == target:
                answer += 1
    return answer

# DFS
def solution(numbers, target):
    n = len(numbers)
    answer = 0
    def dfs(index, value):
        if index == n:
            if value == target:
                nonlocal answer
                answer += 1
            return
        else:
            dfs(index + 1, value + numbers[index])
            dfs(index + 1, value - numbers[index])
    dfs(0, 0)
    return answer