[Programmers] 타겟 넘버 - 43165

첫 dfs 알고리즘 문제 ! recursive function을 이용하여 구한다.

또 다른 방법으로는 from itertools import product를 사용하여 모든 조합에 대한 합을 구한다.

 

Question

 

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

 

Point

• +, - 의 모든 조합을 만들고 from itertools import product를 이용하여 모든 경우의 수의 합을 구함 => Code 1
• dfs algorithm을 이용하여 답을 구함 => Code 2

 

Code 1 : product.

 

product를 이용하여 모든 조합을 만들고 sum한 값을 list에 저장.

from itertools import product
def solution(numbers, target):
    l = [(x, -x) for x in numbers]
    s = list(map(sum, product(*l)))
    return s.count(target)

 

Code 2 : dfs ( Recursion Function )

 

재귀 함수로 dfs 알고리즘 구현.

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

 

now me

On my github