[LV2/DFS] 타겟 넘버

 

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

프로그래머스

 

[풀이]

---

def solution(numbers, target):
    global answer
    answer = 0
    def DFS(L, sum):
        global answer
        if L == len(numbers):
            if sum == target:
                answer += 1
        else:
            DFS(L + 1, sum + numbers[L])
            DFS(L + 1, sum - numbers[L])
    DFS(0, 0)
        
    return answer

• 재귀, 상태트리 개념알면 쉽게 풀리는 문제
• 시간복잡도 생각할 것 없고, answer 자체를 함수 내에서 받아야해서 global을 사용해야했다.
• numbers의 길이와 L(트리 레벨)이 같으면 끝 -> 총 합이 target과 같을 때 answer에 1을 더한다.
• 그 이후로는 재귀로 L+1, sum에 차이를 주며 스택 활용해서 들어가기

 

[풀이 후기]

---

예전에 사뒀던 강의를 들으면서 하고 있는데, 확실히 이해가 정말 잘 되는 것 같다. 재밌다..