[DFS/BFS] 프로그래머스 level 2 타겟넘버 (Python 파이썬)

💡문제 링크

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

프로그래머스

 

 

💡문제 분석 요약

numbers 리스트 속 숫자들을 더하거나 빼서 target 숫자를 만들 수 있는 경우의 수를 출력해야 한다.

 

💡알고리즘 설계

작은 문제로 큰 문제를 해결하는 방안, 즉 재귀함수를 사용하는 코드를 생각했다.

근데 재귀함수를 어떻게 짜야겠다~라는 설계는 머릿속으로 다 되었는데, 코드 구현이 잘 안 되어서

다른 풀이를 참고하였다.

 

💡코드

 

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

 

💡 오답 풀이

...

 

💡 다른 풀이

재귀함수를 활용한 기가 막힌 풀이

def solution(numbers, target):
    if not numbers and target == 0 :
        return 1
    elif not numbers:
        return 0
    else:
        return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])

이건 진짜 대박..

💡 느낀점 or 기억할정보

재귀함수를 쓸 때 매개변수로 뭘 써야할지 생각해내는 게 어렵다..