[python] programmers - 타겟 넘버

오늘은 프로그래머스의

dfs/bfs에 있는 가장 첫 번째 문제

타겟 넘버를 가져왔다.

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

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

 

풀면서 느낀 점은 이 문제는

dfs/bfs보다는 완전 탐색에 가까운 거 같다.

 

1. 아이디어

 

예시를 확인해보면

1, 1, 1, 1, 1이라는 숫자가 주어지고

타겟 넘버가 3일 경우

아래와 같은 경우가 가능하므로

답인 5가 된다.

 

그렇기에

처음 기본값을 0으로 두고

숫자들을 차례로

더하고 빼보는 모든 과정을 하며

마지막 숫자가 계산되었을 때

결괏값을 타켓 넘버와 비교해

정답을 도출했다.

 

2. 코드 구현

answer = 0
 
def solution(numbers, target):
    
    def make(num, now):
        
        global answer
        if now == len(numbers):
            if num == target:
                answer += 1
            return
        
        make(num+numbers[now], now+1)
        make(num-numbers[now], now+1)
    
    make(0, 0)
    
    return answer