[2단계] 타겟넘버

문제 설명

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 이하인 자연수입니다.

입출력 예

numberstargetreturn

[1, 1, 1, 1, 1]

3

5

입출력 예 설명

문제에 나온 예와 같습니다.

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

코딩테스트 연습 - 타겟 넘버

 

def dfs(array, numbers, target, size):
    result = 0
    if len(array) == size:
        if sum(array) == target:
            return 1
        else:
            return 0
    else:
        a = numbers.pop(0)
        for i in [1, -1]:
            array.append(a * i)
            result += dfs(array, numbers, target, size)
            array.pop()
        numbers.append(a)
        return result

def solution(numbers, target):
    answer = 0
    answer += dfs([numbers[0]], numbers[1:], target, len(numbers))
    answer += dfs([-numbers[0]], numbers[1:], target, len(numbers))
    return answer

 

• numbers 리스트 안에 있는 수가 양일 때와 음 일때 모두를 탐색해야 하므로 깊이 우선 방식을 적용한다.
• numbers.append(a)를 해준 이유는 len(array) == size 가 되기 위해 numbers.pop()을 계속 해주기 때문에 마지막 한개가 부족해서 해준 것이다.
• array.pop()을 한 이유는 array.append()한 만큼 pop을 해줘야 다음 계산해야할 것들을 넣을 수 있기 때문이다.