python 코딩테스트 - 타겟 넘버

출처 : 프로그래머스

처음 든 생각

- 모든 경우의 수를 다 돌아야겠네 -> dfs

- 하나씩 더해주거나 빼주는 건데 이전의 결과를 받아야되니깐 -> 재귀함수

이런 식의 아이디어를 구현하기로 생각했다. 

 

나의 답

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

먼저 dfs 함수를 만들어 재귀로 동작하도록 구상을 했기 때문에 dfs의 매개변수를 어떻게 설정할 것인지부터 고민했다.

 

전체 리스트, 이전의 합산 값, 단계수 총 3개의 매개변수를 받도록 하였고 i가 마지막 단계라면 그 때 합산값을 비교하여 target가 맞는지 아닌지 확인하는 과정을 거친다.

 

모든 경우의 수를 다 찾아야하는 경우에는 DFS라는 방식을 떠올리고 그에 맞춰서 어떤 방식으로 함수를 구상할 것인지 고민해보는 좋은 연습이 되었다.