프로그래밍/기타
[프로그래머스][Python3] 타겟 넘버
snoopybox
2019. 11. 11. 00:26
문제 :
https://programmers.co.kr/learn/courses/30/lessons/43165
나의 풀이 :
def solution(numbers, target):
def dfs(target, remain, visit, end):
if abs(target) <= remain:
if visit == end:
if abs(target) == remain:
nonlocal ans
ans += 1
else:
num = numbers[visit]
dfs(target+num, remain-num, visit+1, end)
dfs(target-num, remain-num, visit+1, end)
numbers = sorted(numbers, reverse=True)
ans = 0
dfs(target, sum(numbers), 0, len(numbers)-1)
return ans
한마디 :
모든 경우의 수를 탐색하기에 앞서 가지치기를 위해 역순 정렬을 먼저 해두었다. 큰 수부터 먼저 처리를 해야 나머지 경로를 추가 탐색할 가치가 있는지 빠르게 판단할 수 있다.