[Programmers] 타겟 넘버 (DFS/BFS Lv.2) - Python

1. 문제

---

타겟 넘버

2. 풀이

---

코드

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


def solution(numbers, target):
    global count
    count = 0
    dfs(numbers, 0, target)
    return count

입력 및 출력

numbers	= [4, 1, 2, 1]
target = 4

>> 2

3. 로직

---

1. dfs 함수: 이 함수는 재귀적으로 호출되며, 현재까지의 숫자 합을 나타내는 current_sum, 사용 가능한 숫자들을 나타내는 numbers, 목표 숫자인 target을 매개변수로 받는다. 전역 변수인 count를 사용하여 가능한 방법의 수를 저장한다.

• if not numbers: numbers 리스트가 비어있는 경우를 처리한다. 이는 더 이상 사용 가능한 숫자가 없음을 의미하며, 이때 current_sum이 target과 일치하는지 확인한다. 일치하면 count를 1 증가시킨다.

• dfs(numbers[1:], current_sum + numbers[0], target): 현재 숫자를 더하는 경우를 처리한다. numbers[0]은 현재 선택한 숫자를 나타내며, current_sum에 더해주고, numbers 리스트에서 현재 숫자를 제외한 나머지 숫자들인 numbers[1:]을 재귀적으로 탐색한다.

* dfs(numbers[1:], current_sum - numbers[0], target): 현재 숫자를 빼는 경우를 처리한다. numbers[0]은 현재 선택한 숫자를 나타내며, current_sum에서 빼주고, numbers 리스트에서 현재 숫자를 제외한 나머지 숫자들인 numbers[1:]을 재귀적으로 탐색한다.

2. solution 함수: 이 함수는 주어진 numbers 리스트와 target 숫자를 매개변수로 받는다. 이 함수에서는 전역 변수인 count를 초기화하고, dfs 함수를 호출하여 count 값을 계산한다. 마지막으로 계산된 count 값을 반환한다.

4. 그림

---