프로그래머스)타겟 넘버 - python

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

프로그래머스

 

문제는 간단하다

numbers에 숫자들을 모두 더하거나 빼서 target과 같은 숫자를 만들고, 그 경우의 수를 리턴하는 것이다

처음 봤을 때부터 무슨 알고리즘을 써야할지 감도 오지 않았다.

몇시간을 고민했고 검색 끝에 dfs라는 것을 알았으나

 

정답 코드를 봐도 이해가 되질 않았다

이 한 문제만으로 삼일동안 끙끙 앓아왔고 겨우 이해할 수 있었다.

 

def solution(numbers, target):
    answer = 0
    n = len(numbers)
    
    def dfs(idx, result):
        if idx >= n:
            if result == target:
                nonlocal answer 
                answer += 1
            else:
                return
        else:  
            dfs(idx +1 , result + numbers[idx])
            dfs(idx + 1, result - numbers[idx])
    
    dfs(0,0)
    return answer

dfs를 공부할 때 탈출 조건이 중요하다고 배웠었다.

그 이유는 탈출조건이 명확하지 않을 경우 스택오버플로가 발생하기 때문이다.

탈출 조건부터 설명하자면, 조건은 idx가 len(numbers) 같거나 클 때이다.

즉 dfs(0,0)으로 0번째 인덱스, 그리고 합계(처음 호출하여 실행하는 거니 당연히 result는 0이다)를 인자로 넘겨준다.

넘겨받은 idx가 idx >= len(numbers)일 때, 즉 numbers의 모든 숫자를 더하거나 뺏을 경우, target의 조건을 확인한다

만일 idx >= len(numbers)가 아닐 경우 idx + 1 인덱스와 idx인덱스 번째의 숫자와 result를 더한 값을 넘겨 다시 dfs를 호출한다.

 

즉 dfs(0,0)일경우 idx = 0이고 0은 len(numbers)보다 작으므로 

dfs ( 0+ 1, 넘겨받은 result== 0 + numbers[0] )를 호출한다.

그리고 이경우는 0번째와 1번째를 더한 경우이므로 뺀 경우도 호출한다.

dfs(idx +1 , result + numbers[idx]). ===> 0번째와 1번째를 더한경우

dfs(idx + 1, result - numbers[idx]). ====> 0번째와 1번째를 뺀 경우

 

다시 dfs (1,1)의 경우로 생각해보자.

idx는 1이므로 당연히 탈출조건에 만족하지 않고 

dfs ( 1 + 1, 1 + numbers[1])을 호출한다

이경우 1번째와 2번째를 더한 경우이므로, 당연히 1번째와 2번째를 뺀 경우도 호출해야 한다.

 dfs(idx +1 , result + numbers[idx])
 dfs(idx + 1, result - numbers[idx])