LV 2: 타겟 넘버

문제 링크

LV 2: 타겟 넘버

구현 방식

• 평범한 dfs를 이용한 brute force 문제이다

• 프로그래머스에서 전역변수(global)를 사용하려면 solution 함수 밖에서 쓰고자하는 변수를 define 해줘야한다

코드

way_cnt = 0
def solution(numbers, target):
    global way_cnt
    N = len(numbers)

    def dfs(operator, depth):
        global way_cnt
        
        if depth == N-1:
            tmp_sum = 0
            for i in range(N):
                if operator[i] == '+':
                    tmp_sum += numbers[i]
                else:
                    tmp_sum -= numbers[i]
            if tmp_sum == target:
                way_cnt += 1
            return
        
        dfs(operator + '+', depth+1)
        dfs(operator + '-', depth+1)
             
    dfs('+', 0)
    dfs('-', 0)
    return way_cnt