[프로그래머스] 깊이/너비 우선 탐색(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 이하인 자연수입니다.

입출력 예

 

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

 

 

나의 솔루션 (접근 방법)

 

dfs/bfs 유형 문제는 보자마자 "재귀?" 를 조심스레 묻게 된다. 이번 문제 역시 깊이우선 탐색의 정석이었기 때문에 재귀를 당연히 써야 한다는 가정 하에 접근해 보았다. 

 

가장 포인트가 되었던 부분은 현재 숫자 이후 들어오는 숫자에 + 와 - 가 오는 경우 두 가지 모두를 검토해야 한다는 것이다. 어떤 식으로든 배열이 빈 배열이 될 때까지 숫자를 앞에서부터 하나씩 빼서 +, - 를 붙여야겠다는 생각이 들었다. 배열로 모든 조합을 만들자니 시간 복잡도가 우려되었는데, target 이 정수로 주어졌다는 점이 힌트가 되었다. 

 

target 에서 배열에서 뺀 현재 숫자를 빼거나 더하면 결국 + 와 - 기호를 붙이는 것이나 마찬가지이고, 모든 과정 이후에 target 이 정확히 0이 된다면 이는 해당 숫자들의 (유니크한) 조합으로 target 을 만들 수 있다는 뜻이 되므로 1을 추가해준다. 그렇지 않을 경우, 0 을 추가해 주어 합산될 때 영향을 주지 않도록 한다. 

 

그리하여 완성한 코드이다. 

 

def solution(numbers, target):
    
    if len(numbers) == 0:
        if target == 0:
            return 1
        else:
            return 0
    
    return solution(numbers[1:], target - numbers[0]) + solution(numbers[1:], target - numbers[0] * -1)

 

**추가 설명

numbers = [1,2,3],  target = 6 을 구하고자 하는 경우

target(6) - 1,  재귀([2,3]) 
	target(5) - 2 + 재귀([3])
		target(3) - 3 + 재귀([])  -> target == 0, 1 반환
		target(3) - -3 + 재귀([]) -> target == 6, 0 반환
	target(5) - -2 + 재귀([3])
		target(7) - 3 + 재귀([]) -> target == 4, 0 반환
		target(7) - -3 + 재귀([]) -> target == 10, 0 반환
target(6) - -1 + 재귀([2,3])
	target(7) - 2 + 재귀([3])
		target(4) - 3 + 재귀([]) -> target == 1, 0 반환
		target(4) - -3 + 재귀([]) -> target == 7, 0 반환
	target(7) - -2 + 재귀([3])
		target(9) - 3 + 재귀([]) -> target == 6, 0 반환
		target(9) - -3 + 재귀([]) -> target == 12, 0 반환

결론: 합산하여 얻어지는 수는 1이므로 경우의 수는 1개이다. 

최초 target 에 도달할 수 있는 숫자의 조합을 구하는 방법: 1이 반환되는 재귀에 사용되었던 숫자들의 부호를 반대로 돌리면 된다.

위에 나온 예시의 경우, [+1, +2, +3] 만이 답이 될 수 있다.