[파이썬/알고리즘] 프로그래머스 - 타겟 넘버 (DFS)

[문제 설명]

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

 

[입출력 예]

numbers	target	return
[1, 1, 1, 1, 1]	3	5

 

[풀이]

answer = 0
def DFS(L, sum, numbers, target):
    global answer
    N = len(numbers)
    if L == N:
        if target == sum:
            answer += 1
            return
    else:
        DFS(L+1, sum+numbers[L], numbers, target)
        DFS(L+1, sum-numbers[L], numbers, target)
        

def solution(numbers, target):
    global answer
    DFS(0,0, numbers, target)
    return answer

 

solution 함수를 먼저 보면

나중에 DFS 함수에서 사용해야 하므로 answer를 전역변수로 선언했다. 

다음 줄에서 DFS를 호출한다.

 

DFS 함수는 매개변수로,

L은 Level의 약자 (트리 구조에서의 한 개의 층),

sum은 수의 덧셈과 뺄셈의 결과값(결국 주어진 target과 sum이 같아야 답이 된다.),

주어진 numbers와 target이 있다.

 

이 문제는 cut edge를 하지 않아도 풀리는 문제라서,

Level이 numbers 리스트의 길이와 같을 때 / 같지 않을 때로 구분했다.

 

먼저 같지 않을 때를 보면,

문제에서 주어진대로 sum에 숫자를 더하고 빼면서 재귀 호출한다.

 

Level이 N이 되면서, sum이 target과 같다면,

답에 1 증가시킨다.