프로그래머스(DFS/BFS)-타겟 넘버-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 이하인 자연수입니다.

입출력 예

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

 

---

내 문제풀이

1. numbers 배열의 각 숫자마다 +와 -를 사용한 모든 계산을 수행하기 위해 재귀함수를 활용한 DFS를 구현한다.

2. dfs함수의 인자로는 (numbers 배열의 숫자를 선택할 index, 차례대로 계산 중인 결과 값, numbers, target) 이다.

3. 재귀함수를 호출할 때마다 index는 1씩 증가시키고, 계산은 각 숫자를 + 또는 -하여 수행한다.

4. index가 numbers의 길이와 같아지면 numbers의 모든 숫자를 사용한 것이므로 현재까지의 계산 결과가 target과 같은지 확인하고 해당 함수 주기를 return 0으로 종료한다.

5. 만약 현재까지의 계산 결과가 target과 같다면 answer(타겟 넘버 생성할 수 있는 방법의 수)를 +1 한다.

내 코드-파이썬

answer=0

def dfs(idx, cur, numbers, target):
    global answer
      
    if idx==len(numbers):
        if cur == target:
            answer += 1
        return 0
    
    dfs(idx+1, cur+numbers[idx], numbers, target)
    dfs(idx+1, cur-numbers[idx], numbers, target)

def solution(numbers, target):
            
    dfs(0, 0, numbers, target)
    return answer