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

https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

 

문제

 

 

---

내 풀이

DFS를 활용하는 문제였습니다. 

어느 타이밍에 더하고 빼야하는지 for문을 활용해서 만드려니 헷갈리고 중복되는 경우가 많았는데

오히려 단순하게 재귀 함수를 2번 써서 +인 경우와 -인 경우를 고려하니 더 간결해졌습니다.

종료 조건을 이중 if 문을 활용하여 만드는 것도 많이 헷갈리는 부분이었습니다. 

def solution(numbers, target):
    answer = 0

    def dfs(idx, tot):
        nonlocal answer
        if idx == len(numbers):     
            if tot == target:
                answer+= 1
            return

        dfs(idx+1, tot + numbers[idx])
        dfs(idx+1, tot - numbers[idx])
     
    temp = dfs(0, 0)
    return answer

 

메모

프로그래머스 / 알고리즘 고득점 kit / 깊이/너비 우선 탐색(DFS/BFS / Lv2.