99클럽 코테 스터디 11일차 TIL bfs/dfs : 프로그래머스 LV.2 타겟넘버 with Python

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

프로그래머스

문제는 위쪽에서!

 

def solution(numbers, target):
    answer = [0]
    
    def dfs(cur, i):
        if i == len(numbers):
            if cur == target:
                answer[0] += 1
            return
        
        dfs(cur+numbers[i], i+1)
        dfs(cur-numbers[i], i+1)
            
    dfs(0, 0)
    
    return answer[0]

 

재귀함수를 사용해서 문제를 풀었다.

cur은 현재까지 더하거나 뺀 숫자들의 합이고 numbers에 있는 숫자들을 더하고 빼면서 모든 숫자들을 더하고 뺐을 때의 결과값이 타겟값과 같다면 1을 올려주는 형식으로 풀었다.