📃 문제 설명

타겟 넘버

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

[문제 출처 : 프로그래머스]

👨‍💻 해결 방법

나의 생각의 흐름을 주절주절..

+와 - 둘 중 선택하여 계산해 나간다.
그래프 문제로 생각할 수 있었다.

BFS, DFS 두 방법으로 풀 수 있지만
나는 제일 먼저 DFS 방식이 떠올랐다.

우선 주어진 수의 - ,+를 스택에 넣고,(그래프의 level과 함께)
스택이 빌 때까지 반복문을 돈다.

pop한 결과에 level을 더하고 -, +결과를 각각 푸시한다.

그렇게 돌다가 level이 주어진 수에 도달하면 그 때의 level에 있는 값들 중에 타겟 넘버와 같은 것들의 개수를 세면 된다.

결론

스택에 튜플 형태로 (level, value)를 저장한다.
레벨을 더해가며 value에는 다음 수를 -,+각각 계산하여 스택에 푸시해간다.

스택을 사용하기 때문에 DFS방식으로 돌게 될거고 level이 주어진 수만큼 도달하면 그 level에 있는 노드의 value중 타겟 넘버와 일치하는 개수를 세면 된다.

👨‍💻 소스 코드

def solution(numbers, target):
    answer = 0

    stack = [[0, -numbers[0]], [0, numbers[0]]]

    while stack:
        i, value = stack.pop()
        i += 1
        if i < len(numbers):
            stack.append([i, value - numbers[i]])
            stack.append([i, value + numbers[i]])
        else:
            if value == target:
                answer += 1
    return answer