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

티스토리 메뉴 펼치기 댓글수0

프로그래밍/기타

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

snoopybox
댓글수0

문제 :

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


나의 풀이 :

def solution(numberstarget):
    def dfs(targetremainvisitend):
        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), 0len(numbers)-1)
    return ans


한마디 :

모든 경우의 수를 탐색하기에 앞서 가지치기를 위해 역순 정렬을 먼저 해두었다. 큰 수부터 먼저 처리를 해야 나머지 경로를 추가 탐색할 가치가 있는지 빠르게 판단할 수 있다.


맨위로

https://www.snoopybox.co.kr/2055

신고하기