[프로그래머스/python] 깊이/너비 우선 탐색(DFS/BFS) : 타겟 넘버

문제 설명

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

• -1+1+1+1+1 = 3
• +1-1+1+1+1 = 3
• +1+1-1+1+1 = 3
• +1+1+1-1+1 = 3
• +1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

 

정답

def solution(numbers, target):
    answer = 0

    sum = [[] for _ in range(len(numbers))]
    sum[0].append(numbers[0])
    sum[0].append(-numbers[0])

    for i in range(1, len(numbers)):
        for k in sum[i - 1]:
            sum[i].append(k + numbers[i])
            sum[i].append(k - numbers[i])

    return sum[len(numbers)-1].count(target)

---

이차원 배열 sum을 만든다. 첫번째 인덱스는 연산에 사용된 숫자의 개수-1을 의미한다.

예를 들어, 1개 숫자만 사용하여 연산할 경우 sum[0]에 저장하고 마지막 숫자의 인덱스는 0이 된다.

2개 숫자를 사용하여 연산할 경우 sum[1]에 저장하고 마지막 숫자의 인덱스는 1이 된다.

첫번째 숫자만 사용할 경우인 numbers[0]과 -numbers[0]을 sum[0]에 저장한다.

 

반복문을 이용하여 해당 숫자를 추가하여 연산헀을 때를 sum[i]에 저장한다.

해당 숫자를 추가하지 않았을 때는 인덱스-1까지 연산했음을 의미하므로

sum[i-1]의 모든 값에 해당 숫자 numbers[i]를 더하거나 뺀 값을 sum[i]에 저장한다.

 

sum[len(numbers)-1]은 모든 숫자를 사용하여 연산한 모든 경우가 들어있으므로

이 중 값이 target과 같은 값만 count하여 return 한다.