코딩테스트 연습/프로그래머스

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

슈퍼짱짱 2023. 8. 7. 16:09
반응형

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

 

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 


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한다.

반응형