타겟넘버

it 취업을 위한 알고리즘 문제 풀이

문제

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

[

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

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+

programmers.co.kr

](https://programmers.co.kr/learn/courses/30/lessons/43165)

코드

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

res = 0

def DFS(numbers,depth,targetNum,total):
    if depth == len(numbers):
        if total == targetNum:
            global res
            res += 1
        return

    total += numbers[depth]
    DFS(numbers,depth+1,targetNum,total)
    total -= numbers[depth]

    total -= numbers[depth]
    DFS(numbers,depth+1,targetNum,total)
    total += numbers[depth]



def solution(numbers, target):

    DFS(numbers,0,target,0)

    return res

문제해결방법

• DFS 풀이
  • depth가 index와 같다고 할 때 깊이우선 탐색을 하면서 해당 depth에 해당하는 숫자를 더하거나 빼면서 부모노드까지 누적된 값에서 현재 노드의 값을 계산한다.  계산방법은 아래와 같다. 이렇게 이진트리로 depth(index)가 주어진 리스트의 길이가 될 때까지 그래프 탐색을 진핸한다. 
  • depth(index)가 주어진 리스트의 길이가 될 때까지 해당 뎁스에서 +numbers[depth], -numbers[depth]를 하면서 이진트리로 가지를 뻗어나가고 부모노드의 total에 현재 노드의 depth에 해당하는 숫자를 누적한다.
  • depth가 주어진 리스트의 길이가 되면 지금까지 누적한 값이 타겟넘버와 같은지 비교하고 같으면 반환 할 res변수 값을 하나 증가시킨다.
  • 그리고 재귀함수가 리턴하면 기존의 더한값은 빼주고 기존에 뺀값은 더해주면서 다시 다음노드로 탐색을 진행할기전 초기화를 해준다.