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

문제

• N개의 양수를 순서를 바꾸지 않고 더하거나 빼서 타겟 넘버 만들 수 있는 경우의 수 구하기
  • 2 <= N <= 20
  • 1 <= 각 숫자 <= 50
  • 1 <= 타깃 넘버 <= 1000

 

풀이

• 덧셈, 뺄셈 2개 경우에 대해 최대 20개 숫자가 있으므로 전체 경우의 수를 확인한다면 $O(2^20)$ 으로 충분하다
• DFS 이용해서 전체 경우에 대해 타깃 넘버 만들 수 있는지 확인하기!

 

answer = 0
def solution(numbers, target):
    def dfs(depth, numbers, now):
        global answer
        if depth == 0 :			# 모든 숫자 사용했고,
            if now == target:	# 타깃 넘버 만들 수 있으면
                answer += 1		# 정답 +1
            return
        dfs(depth-1, numbers[1:], now+numbers[0])	# 현재 기호 +
        dfs(depth-1, numbers[1:], now-numbers[0])	# 현재 기호 -
        
    dfs(len(numbers), numbers, 0)
    return answer

 

 

 

References

• 프로그래머스 고득점 Kit DFS/BFS