[파이썬] 타겟 넘버 [CODING TEST #21]

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

 

 

DFS로 해결했다. +number와 -number로 진행해서 끝까지 갔을 때 target과 일치하면 answer의 값이 1 증가하도록 함.

 

def dfs(numbers, target, length):
    answer=0
    if length==len(numbers): # 마지막 도착
        if sum(numbers) == target: # Target과 일치?
            return 1
        else: return 0
    else:
        answer += dfs(numbers,target,length+1) # +number
        numbers[length] *= -1
        answer += dfs(numbers,target,length+1) # -number
        return answer
    
def solution(numbers, target):
    answer = dfs(numbers,target,0)
    return answer

 

BFS로 해결한 풀이도 찾아 보았다. 빈 리스트에 +,-값들을 더한 누적합을 저장하면서 sum_list를 갱신하는 기발한 방법이다.

 

def solution(numbers, target):
    answer = 0
    sum_list = [0]
    for num in numbers:
        temp = []
        for t in sum_list:
            temp.append(t + num)
            temp.append(t - num)
        sum_list = temp
    for sums in sum_list:
        if sums == target:
            answer += 1
    return answer