프로그래머스 타겟넘버

문제 설명

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]	3	5

풀이

count = 0
def dfs(n, numbers, target): 
    global count
    if not numbers:
        if n == target:
            count += 1
    else:
        dfs(n+numbers[0], numbers[1:], target)
        dfs(n-numbers[0], numbers[1:], target)
    
def solution(numbers, target):
    dfs(0,numbers,target)
    answer = count
    return answer

DFS 와 BFS의 특징

• 트리로 문제를 구현해야하며 최하단의 모든 노드의 값들이 필요하기 때문에 입력되는 데이터의 크기가 크지 않다.
• 위와 같은 이유로 모든 값을 구하기 위해 재귀를 많이 사용함

순서

1. 전역 변수로 count를 선언해둔다.
2. dfs 함수에 number와 target과 함께 현재까지의 계산 결과를 저장할 n값을 같이 보내준다.
3. dfs함수 안에서 number가 없으면 조건을 넣어준다.(최하단 노드까지 도착했다는 뜻 = 모든 값들을 연산에 넣었다.)
4. 그 상태에서 최종 노드값이 target값과 일치하면 count에 1을 더해준다.
5. 만약 최종 노드까지 도달하지 못한 것이라면 값을 양수로 계산했을 경우 하나 음수로 계산했을 경우하나 이렇게 두가지의 값을 가지고 재귀함수를 실행한다.
6. 재귀함수를 돌리기 전 n 값에는 현재 인덱스 위치의 값을 더해주거나 뺴주며, numbers 배열같은 경우는 현재 계산된 값을 제외한 다음 인덱스부터 끝까지의 배열을 다시 보내준다.