[프로그래머스] 타겟 넘버 파이썬 풀이

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

프로그래머스

---

1. 풀이

• 완전 탐색이 가능한가?

주어진 숫자의 개수는 최대 20개이다. 모든 원소를 더하거나 빼는 경우를 고려할 때, 최악의 경우에도 2^20번만 연산하면 된다. 이는 10^6 정도인데, 이 정도는 시간 초과 없이 계산할 수 있다.

 

 

• 모든 숫자를 더하고, 빼는 과정을 재귀로 돌리자

재귀 함수의 종료 조건은 index가 numbers 리스트의 길이 이상일 때이다. 만약 종료 조건에서 지금까지 재귀 함수를 호출하면서 누적된 결과가 target과 동일하면 +1 아니면 그냥 넘어간다.

종료 조건이 아니라면, numbers[index]를 더하는 경우와 빼는 경우에 대해 다시 재귀 함수를 호출한다.

 

 

 

2. 정답 코드

answer = 0
def solution(numbers, target):
    def dfs(index, result):
        global answer
        if index >= n:
            if result == target:
                answer += 1
            return
        
        dfs(index + 1, result + numbers[index])
        dfs(index + 1, result - numbers[index])
    
    n = len(numbers)
    dfs(0, 0)
    return answer

 

위 코드에서 글로벌 변수를 사용하지 않으면서 더 간단명료하게 작성할 수도 있다.

 

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