[프로그래머스] 타겟 넘버

programmers.co.kr/learn/courses/30/lessons/43165

코딩테스트 연습 - 타겟 넘버

---

문제 설명

1. 배열 변수인 numbers가 주어진다. ex) [1, 3, 4, 5, 2]

2. int형 변수인 target이 주어진다.

3. 각 numbers를 무작위로 더하거나 빼서 target 값과 같은 개수는?

 

문제 풀이

1. 모든 경우의 수를 찾아야 하므로 완전 탐색 문제 입니다.

2. 더하거나 뺐을 때 나오는 값을 재귀적으로 실행시킵니다.

3. 경우의 수가 만들어질 때 마다 target 값과 sum 값이 같은지 비교후 리턴 합니다.

  - 같다면, cnt를 1씩 올려줍니다.

4. cnt를 정답으로 제출합니다.

 

코드

def solution(numbers, target):
    def DFS(L, sum):
        nonlocal cnt
        if L == len(numbers):
            if sum == target:
                cnt += 1
            return
        else:
            plus = sum + numbers[L]
            DFS(L + 1, plus)
            minus = sum - numbers[L]
            DFS(L + 1, minus)
            
    cnt = 0
    DFS(0, 0) 
    return cnt