[Python - 프로그래머스] 타겟 넘버

파이썬으로 코딩테스트 연습 :: 프로그래머스 타켓넘버

 

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

프로그래머스

 

---

Solution

 

def solution(numbers, target):
    def dfs(numbers, i, value1, value2) :

        if i == len(numbers)-1 :
            return (value1 == target) + (value2 == target)
        l = dfs(numbers, i+1, value1+numbers[i+1], value1-numbers[i+1])
        r = dfs(numbers, i+1, value2+numbers[i+1], value2-numbers[i+1])

        return l+r
    return dfs(numbers,0,numbers[0],-numbers[0])

 

문제에 BFS, DFS라고 힌트를 줬기때문에 DFS로 문제를 풀었다.

 

numbers의 첫 번째 원소부터 시작하여 +일때와 -일때는 각각 value1, value2로 전달한다.

value1에 다음 원소를 마찬가지로 더하고 빼고, value2에도 다음 원소를 더하고 뺀다.

 

마지막 원소까지 실행 한 후 value1과 value2 중 target과 동일한 개수를 return한다.