[ Programmers 43165 ] 타켓넘버(Python)

문제

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

주어진 숫자리스트 numbers 를 더하고 빼서, 타켓 넘버가 될 수 있는 방법의 수를 구하는 문제다.

트리 형태로 생각을 하니 조금 쉬었다.

문제 풀이

그림을 보면 이해가 더 쉬울 것 같아서 만들어보았다.
nums에 접근할 index와 숫자를 더한 변수 total를 이용해줄 것이다.

1. 우선 index가 numbers 리스트의 길이와 같아질때까지 dfs 함수를 호출한다.
2. 이때 dfs를 호출할때는 [total에 numbers[index]를 더하거나 빼준 값 ] 과 index+1을 함께 넣어준다.

ret += dfs(index+1,total+numbers[index])
ret += dfs(index+1,total-numbers[index])

3. 이렇게 index의 길이가 numbers 리스트의 길이와 같아졌을 때 total과 target이 같으면 1을 return 한다.

4. return한 값은 ret 변수에 모두 더해준다.

5. ret 변수를 return 해준다.

코드

import collections

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