[programmers] Level 2 타겟 넘버.py

프로그래머스 Level 2 타켓 넘버를 파이썬을 통해 풀어보았다. 

 

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

코딩테스트 연습 - 타겟 넘버

타겟 넘버.py

tomy9729/Algorithm

Level 2 - 타겟 넘버

DFS로 해결할 수 있는 문제이다. 각 단계들을 탐색하며 한번은 더해주고 한번은 빼준다. 마지막 단계까지 왔을 때 target 값과 같다면 answer을 하나 증가시킨다.

 

DFS로 분류되어 있는 문제라 굳이 DFS로 풀어봤지만 재귀 함수나 DP로도 풀 수 있을 듯 하다.

#Level 2 타겟 넘버.py
def solution(numbers, target):
    answer = 0
    def DFS(num, level) : 
        nonlocal answer
        if level == len(numbers) :
            if num == target : 
                answer += 1
            return
        if level == 1 : 
            DFS(num+numbers[level],level+1)
            DFS(num-numbers[level],level+1)
            DFS(-1*num+numbers[level],level+1)
            DFS(-1*num-numbers[level],level+1)
        else :
            DFS(num+numbers[level],level+1)
            DFS(num-numbers[level],level+1)
    DFS(numbers[0],1)
    return answer