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

문제를 정리해보자.

 

n개의 음이 아닌 정수가 있다. 이 수들을 적절히 더하거나 빼서 원하는 숫자를 만들려고 한다.

예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들어보자.

 

 

프로그래머스 예시

 

 

위와 같이 5가지 방법이 있다.

 

주의해야 할 점은 연산순서가 바뀐다고 경우의 수가 늘어나지 않는다.

예를 들어 [1, 2, 3]으로 -6을 만든다고 해보자. -1-2-3, -2-1-3, -3-2-1등 다 같은 경우이다.

 

 

풀이를 생각해보자.

 

예를 들어 [1, 1, 2, 3]을 가지고 있다고 해보자.

 

 

[1, 1, 2, 3]

 

 

1. 시작은 1, 2, 3중 하나로 잡는다. (사진에서는 1로 잡았다. 하나를 잡아야 중복되는 결과가 나오지 않는다.)

2. 누적값에 해당 수로 +와 -연산한다. (누적값이 없다면 0으로 시작)

3. 그 값을 누적시킨다.

4. 잡지 않았던 수를 잡는다.

 

모든 경우의 수가 나올 때까지 2~4번을 반복한다.

 

 

구현해보자.

 

BFS로 구현했다.

 

 

def solution(numbers, target):

    accumulate = [0]  # 계산 결과 누적

    for num in numbers:
        tmp = []
        for parent in accumulate:
            tmp.append(parent + num)
            tmp.append(parent - num)
        accumulate = tmp

    return accumulate.count(target)


solution([1, 1, 1, 1, 1], 3)

 

 

시간 복잡도는 O(2^N)이다.