타켓 넘버 - level2

def solution(numbers, target):
    answer = 0
    dp = [0]
    for i in numbers:
        temp = []
        for j in dp:
            temp.append(j+i)
            temp.append(j-i)
        dp = temp
    return dp.count(target)

 

생각해보면 각 인덱스의 값을 -와 +로 나눠가면서 더하는 트리처럼 뻗어나가는 형식의 문제이다.

 

< 1,1,1,1,1 일 경우 >

 

첫번째 인덱스 값에 0가 -와 +를 한 값을 temp에 넣는다. 이후 dp에 값을 다시 넣어주면  -1과 +1이 들어가 있을 것이다. 

 

두번째 인덱스 값에 -1과 1에 각각 -와 +한 값을 넣는다. 그럼 -2, 0, 2, 0이 temp에 들어갈 것이다. 다시 dp에 temp를 덮어씌운다.

 

이 과정을 반복하면 결국 가장 마지막의 모든 경우의 결과가 들어갈 것이다. 그 값중 target의 값만 카운팅 해주면 된다.

 

BFS와 같이 계산된 값을 내부에 넣고 하나씩 뺴서 계산한 결과를 다시 넣고를 반복하는 방식을 이용했다.