(Python) - 프로그래머스 : 타겟 넘버

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

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

 

• 해설 :

사용할 수 있는 수들이 담긴 배열과 targetNumber가 주어질 때 주어진 배열의 수들을 덧셈 혹은 뺄셈 연산하여 타겟 넘버를 만들 수 있는 경우의 수를 찾는 문제이다.

 

 

 

• 풀이 :

DFS(깊이우선 탐색)를 사용해서 해결할 수 있는 문제이다.  재귀함수의 매개변수로 현재 값, 현재 값을 만들기 위해 사용한 연산의 수,  비교할 targetNumber를 넘겨주었고 모든 수를 사용하였을 때 targetNumber를 만들었다면 answer을 1씩 카운팅해주었습니다.

 

 

 

 

answer = 0
number = []
def dfs(curr,i,target):
    global answer
    if curr == target and i == len(number):
        answer += 1
        return 
    if i < len(number):
        dfs(curr+number[i],i+1,target)
        dfs(curr-number[i],i+1,target)
    
def solution(numbers, target):
    global number,answer
    number = numbers
    dfs(0,0,target)
    return answer