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

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

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

문제 설명

이 문제는 그래프로 접근 할 수 있다. 

DFS또는 BFS를 활용하면 된다 (DFS가 더 빠르다)

해당 코드는 DFS로 풀었다

 

 

코드 구현

python3 으로 풀었다.

answer =0

def dfs(index, numbers, sum, target):
    global answer
    n=len(numbers)
    #끝에 도달했으면
    if(index == n-1):
        #sum 값이 target값과 일치하면 answer++
        if(sum == target):
            answer+=1
    #끝이 아니라면
    else:   
        dfs(index+1 , numbers, sum+numbers[index+1],target)
        dfs(index+1 , numbers, sum-numbers[index+1],target)

def solution(numbers, target):
   
    dfs(-1,numbers,0,target)
    print(answer)
    return answer



numbers=[1, 1, 1, 1, 1]
target = 3
solution(numbers,target)