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

** 개인적 공부를 위한 포스팅일 뿐이므로 신뢰성은 보장할 수 없다.

** 30분 안에 풀었으면 Mastered 카테고리이다.

 

문제에 대한 이해

각 리스트 원소 별로 플러스 연산과 마이너스 연산 중에 하나만 택하면 되기 때문에 간단한 상태 트리를 그려보면 이해가 쉽다. 정석적인 DFS 문제이다.

 

나의 풀이

def solution(numbers, target):
    answer = 0
    
    def dfs(depth, result):
        nonlocal answer
        if depth == len(numbers):
            if result == target:
                answer += 1
            return
        else:
            dfs(depth+1, result+numbers[depth]) // 플러스 연산을 할 경우
            dfs(depth+1, result-numbers[depth]) // 마이너스 연산을 할 경우
        
    dfs(0, 0)
    
    return answer

depth라는 변수를 두어 모든 원소를 다 검토하고 난 뒤에 target과 result가 같은지를 비교하게 한다.

 

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